• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode406.根据身高重建队列|QueueReconstructionbyHeight

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:为敢(WeiGanTechnologies)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10311344.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意:
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

128ms
 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3         let ps = people.sorted { p1, p2 in
 4           if p1[0] == p2[0] { return p1[1] < p2[1] }
 5           return p1[0] > p2[0]
 6         }
 7         var result: [[Int]] = []
 8         for p in ps {
 9           result.insert(p, at: p[1])
10         }
11         return result
12     }
13 }

136ms

 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3         guard !people.isEmpty else { return [] }
 4         var sortedPeople = people.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] > $1[0] }
 5         var curr = sortedPeople[0][0]
 6         var bucket = [sortedPeople[0]]
 7         var peopleHeightBuckets = [[[Int]]]()
 8         for person in sortedPeople[1...] {
 9             if person[0] == curr {
10                 bucket.append(person)
11             } else {
12                 peopleHeightBuckets.append(bucket)
13                 curr = person[0]
14                 bucket = [person]
15             }
16         }
17         peopleHeightBuckets.append(bucket)
18         
19         var queue = [[Int]]()
20         queue.reserveCapacity(people.count)
21         queue.append(contentsOf: peopleHeightBuckets[0])
22         for bucket in peopleHeightBuckets[1...] {
23             for person in bucket {
24                 queue.insert(person, at: min(person[1], queue.count))
25             }
26         }
27         return queue
28     }
29 }

140ms

 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3         var people = people
 4         people.sort(by:{(a:[Int],b:[Int]) in 
 5         return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1])})
 6         for i in 0..<people.count
 7         {
 8             var p:[Int] = people[i]
 9             if p[1] != i
10             {
11                 people.remove(at:i)
12                 people.insert(p, at: p[1] )
13             }
14         }
15         return people
16     }
17 }

160ms

1 class Solution {
2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
3         var res = [[Int]]()
4         people.sorted(by: { ($0[0] == $1[0]) ? $0[1] < $1[1] : $0[0] > $1[0]                    }).forEach({res.insert($0, at: $0[1])})
5         return res
6     }
7 }

168ms

 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3         let people = people.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] > $1[0] }
 4         var result = [[Int]]()
 5         
 6         for person in people {
 7             result.insert(person, at: person[1])
 8         }
 9         
10         return result
11     }
12 }

368ms

 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3         let sorted = people.sorted {
 4             if $0.first! == $1.first! {
 5                 return $0.last! < $1.last!
 6             } else {
 7                 return $0.first! > $1.first!
 8             }
 9         }
10         
11         var res = [[Int]]()
12         
13         loop: for person in sorted {
14             var num = 0
15             for i in 0..<res.count {
16                 if num == person.last! {
17                     res.insert(person, at: i)
18                     continue loop
19                 }
20                 num += 1
21             }
22             
23             res.append(person)
24         }
25         
26         return res
27     }
28 }

1164ms

 1 import Foundation
 2 
 3 class Solution {
 4   func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 5     let sortedPairArray = people.sorted { (pair1, pair2) -> Bool in
 6       var diff = pair1[0] - pair2[0]
 7       if diff == 0 {
 8         diff = pair1[1] - pair2[1]
 9       }
10       return diff < 0
11     }
12 
13     let peopleCount = people.count
14     var outputArray = Array(repeating: [Int.max, 0], count: peopleCount)
15     for pair in sortedPairArray {
16       let index = findIndex(existingArray: outputArray, pair: pair)
17 
18       if index >= 0 {
19         outputArray[index][0] = pair[0]
20         outputArray[index][1] = pair[1]
21       }
22     }
23     return outputArray
24   }
25 
26   func findIndex(existingArray: [[Int]], pair: [Int]) -> Int {
27     let peopleCount = existingArray.count
28     var count = 0
29     for i in 0..<peopleCount {
30       if count == pair[1] {
31         for j in i..<peopleCount {
32           let existingPair = existingArray[i]
33           if existingPair[0] == Int.max {
34             return j
35           }
36         }
37       }
38 
39       let existingPair = existingArray[i]
40       if existingPair[0] >= pair[0] {
41         count += 1
42       }
43     }
44     return -1
45   }
46 }

2140ms

 1 class Solution {
 2     func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
 3        var res = [[Int]](repeating: [Int](), count: people.count)
 4        var arr = people 
 5         arr.sort {$0.first! < $1.first!} 
 6        for item in arr {
 7            let number = item.last!
 8            let height = item.first!
 9            var count = 0
10            for i in 0..<res.count {
11                let slot = res[i]
12                if slot.count == 0 || slot.first! >= height {    
13                    if count == number {
14                        res[i] = item
15                    }
16                    count += 1
17                }
18            }
19        }
20         return res
21     }
22 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode160.相交链表|IntersectionofTwoLinkedLists发布时间:2022-07-13
下一篇:
Swift3.0 - 集合发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap