LeetCode406. 根据身高重建队列-Java&Go：排序&插入

• 算法
  • 1.排序people数组，person[0]降序，person[1]升序
  • 2.从高往低遍历数组，最高的人的person[1]即是它重建后的位置，如果已经有人，将它插入，后序右移（因为后序的都是先插入的都比它高）
    • 当list中第person[1]个位置尚未填充时，填充该person
    • 当list中第person[1]个位置已经填充时，插入该person，后序右移

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (p1, p2) -> (p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0]));
    ArrayList<int[]> list = new ArrayList<>(Collections.nCopies(people.length, null));
    for (int[] person : people) {
        int k = person[1];
        if (list.get(k) == null) {
            list.set(k, person);
        } else {
            list.add(k, person);
        }
    }
    for (int i = 0; i < people.length; i++) {
        people[i] = list.get(i);
    }
    return people;
}

type Int2DSlice [][]int
func (p Int2DSlice) Len() int { return len(p) }
func (p Int2DSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p Int2DSlice) Less(i, j int) bool {
    if p[i][0] == p[j][0] {
        return p[i][1] < p[j][1]
    } else {
        return p[i][0] < p[j][0]
    }
}

func reconstructQueue(people [][]int) [][]int {
    sort.Sort(Int2DSlice(people))
    result := make([][]int, len(people))
    for _, person := range people {
        k := person[1]
        for j := 0; j < len(people); j++ {
            if result[j] == nil || result[j][0] >= person[0] {
                k--
            }
            if k == -1 {
                result[j] = person
                break
            }
        }
    }
    return result
}

• 算法
  • 1.排序people数组，person[0]升序
  • 2.从低往高遍历数组，最低的人位置先确定，后序接着确定第二低的人
    • 最低的人的位置就是它的person[1]，这个person[1]的含义指的是：从左往右计数，尚未填充person的和填充person的比它高或等高的，这种算上，第person[1]个

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (p1, p2) -> (p1[0] == p2[0] ? p2[1] - p1[1] : p1[0] - p2[0]));
    List<int[]> list = new ArrayList<>(Collections.nCopies(people.length, null));
    for (int[] person : people) {
        int k = person[1];
        for (int j = 0; j < people.length; j++) {
            if (list.get(j) == null || list.get(j)[0] >= person[0]) {
                k--;
            }
            if (k == -1) {
                list.set(j, person);
                break;
            }
        }
    }
    for (int i = 0; i < people.length; i++) {
        people[i] = list.get(i);
    }
    return people;
}

type Int2DSlice [][]int
func (p Int2DSlice) Len() int { return len(p) }
func (p Int2DSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p Int2DSlice) Less(i, j int) bool {
    if p[i][0] == p[j][0] {
        return p[i][1] < p[j][1]
    } else {
        return p[i][0] > p[j][0]
    }
}

func reconstructQueue(people [][]int) [][]int {
    sort.Sort(Int2DSlice(people))
    result := make([][]int, len(people))
    for _, person := range people {
        k := person[1]
        if result[k] == nil {
            result[k] = person
        } else {
            temp := result[k]
            for i := k; i < len(result) - 1 && result[i] != nil; i++ {
                result[i+1], temp = temp, result[i+1]
            }
            result[k] = person
        }
    }
    return result
}