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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 }