2020年6月6日 星期六

Leetcode題解 Python & C#：六月挑戰DAY6 Queue Reconstruction by Height

給一個串列 people ， 其中每一個元素為 (h, k)，h 代表自身的高度， k 代表自身前方有 k 個人的 h >= 自身。
people目前是亂的，要回傳照規則(即每個位置與其 h, k 值皆是對的)排列的串列。 

我沒有第一時想通，看了一下別人的題解。

卡在我只有想到 brute force，但沒有想到要如何簡化。

按照逆向的想法，預想本來會有一個原形只有身高的排列，然後從身高小到大從後方取出，並標上其位置(前方有位置號個比自己 h >=)

所以逆向回去，即身高由高到矮，從前方排，依序一個個放入。

由於是按身高高到矮放入，因此直接把整理好的 people 按其 people[i][1] 去 insert(people[i][1], people[i]) ，即可確保前方有 people[i][1] 比自身高或同。
而輪到較矮的 insert() 也不會影響其排列的正確性，就能順利逆向回所求。

Python 
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        result = []
        for p in people:
            result.insert(p[1], p)
        return result
C# 
public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        var sorted = people.OrderBy(x => (-x[0], x[1])).ToArray();
        var result = new List();
        foreach(var pair in sorted)
        {
            result.Insert(pair[1], pair);
        }
        return result.ToArray();
    }
}
於
標籤： , ,