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

发布时间：2020-12-14 05:05:25 所属栏目：百科来源：网络整理

导读：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 th

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,[6,2]]

Output:
[[5,2],1]]

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

注意：
总人数少于1100人。

示例

输入:
[[7,2]]

输出:
[[5,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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!