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

概述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

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 result12     }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 queue28     }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] != i10             {11                 people.remove(at:i)12                 people.insert(p,at: p[1] )13             }14         }15         return people16     }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 res6     }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 result11     }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 = 015             for i in 0..<res.count {16                 if num == person.last! {17                     res.insert(person,at: i)18                     continue loop19                 }20                 num += 121             }22             23             res.append(person)24         }25         26         return res27     }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 < 011     }12 13     let peopleCount = people.count14     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 outputArray24   }25 26   func findindex(existingArray: [[Int]],pair: [Int]) -> Int {27     let peopleCount = existingArray.count28     var count = 029     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 j35           }36         }37       }38 39       let existingPair = existingArray[i]40       if existingPair[0] >= pair[0] {41         count += 142       }43     }44     return -145   }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 = 010            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] = item15                    }16                    count += 117                }18            }19        }20         return res21     }22 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode406. 根据身高重建队列 | Queue Reconstruction by Height全部内容，希望文章能够帮你解决[Swift]LeetCode406. 根据身高重建队列 | Queue Reconstruction by Height所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。