QueueReconstructionByHeightOPT [source code]

public class QueueReconstructionByHeightOPT {
static
/******************************************************************************/
public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0)
            return people;

        int[][] buf = mergeSort(people);

        List<int[]> res = new ArrayList<>(people.length);

        res.add(buf[0]);

        for (int i = 1; i < buf.length; i++)
            res.add(buf[i][1],buf[i]);

        res.toArray(buf);
        return buf;
    }

    private int[][] mergeSort(int[][] input) {

        if (input == null || input.length < 2)  //Sorting pre-check
            return input;

        int[][] buffer = new int[input.length][input[0].length];    //Create buffer array
        for (int i = 0; i < input.length; i++)  //Initiate buffer array with Deep Copy
            buffer[i] = input[i];

        mergeSorting(input, 0, input.length, buffer);   //Split merge sort

        return input;
    }

    private void mergeSorting(int[][] input, int start, int end, int[][] buffer) {

        if (end - start < 2)    // If run size == 1
            return;       // Consider as sorted

        int mid = (start + end) / 2;

        // Recursively sort both half arrays BUT from buffer into input
        // In this way, we don't have to update the other array after the merge
        mergeSorting(buffer, start, mid, input);    //Sort left array
        mergeSorting(buffer, mid, end, input);      //Sort right array

        int i = start;
        int j = mid;

        for (int k = start; k < end; k++) {
            if (i < mid && (j >= end || buffer[i][0] > buffer[j][0]))
                input[k] = buffer[i++];
            else if (i < mid && (j >= end || buffer[i][0] == buffer[j][0]))
                input[k] = buffer[i][1] < buffer[j][1] ? buffer[i++] : buffer[j++];
            else
                input[k] = buffer[j++];
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        QueueReconstructionByHeightOPT.Solution tester = new QueueReconstructionByHeightOPT.Solution();
        int[][][] inputs = {
            {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}}, {{5,0}, {7,0}, {5,2}, {6,1}, {4,4}, {7,1}},
            {}, {}, 
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[][] nums = inputs[2 * i];
            String input = Matrix.printMatrix(nums);
            String output = Matrix.printMatrix(tester.reconstructQueue(nums));
            String expected = Matrix.printMatrix(inputs[1 + 2 * i]);
            System.out.println(Printer.seperator());
            System.out.println(Printer.wrapColor(input, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output.equals(expected) ? "green" : "red"));
        }
    }
}

这个是submission最优解, 丧心病狂的10(100).

核心思路其实跟普通的discussion最优解还是一样的, 唯一的差别好像就是这里的sort是自己手动实现的; 主要还是学习学习他这里MergeSort的实现方式; 注意他这里start和end这两个index的选择方式: 是类似substring这种的, start被包含, 但是end不被包含的设置方式; 这样的一个方式的好处就是你看他recursive call的时候, mid就直接可以一个division就行了, 可以把稳的知道不会出问题;

这个算法比较折腾的一个地方就是他参数里面用了两个array. 实际上他这个算法也并没有做到InPlace, 他在每一个iteration实际上还是从一个array sort到另外一个array里面的; 但是他的做法跟普通的MergeSort不同的是, 他的这个buffer的array不是每一个iteration new一个出来, 而是作为一个类似accum的形式始终传下去, 然后传上来;

从逻辑的角度上, 感觉他这个算法不是特别好理解; 不过从visual的角度上, 还是可以大概看懂一些的, 就是当前过来的是input和buffer两个array, 然后这个iteration结束的时候我们要用buffer sort到input里面去, 所以在下面的一个level要完成的就是要让buffer已经被sorted. 这个也是为什么recursive call的时候要互换两个array的位置: 这个算法的invariant是each iteratation returns with input/arg0 sorted. 所以你在我们这个level把buffer作为arg0给传下去, 那么上行返回上来的时候你就可以肯定, buffer已经是sorted了;

这里有一个难以理解的地方: recursive call上行返回过来的时候, input是什么状态呢? 这个其实我到现在也没有想通, 不过其实是无所谓的, 因为我们最终只要在乎buffer is sorted when back to this level就行了, 无论上行返回上来的时候input是什么状态都无所谓, 因为我们反正要用buffer来override input了;

打印了一下trace, 大概理解了一点.

反正这个recursion在下行的时候是没有什么变化的, 两个array直接传到底下, 然后上行的时候, 两个array其实是交替对换的. 从下往上数, ith level结束的时候, 它的input是sorted的; 这个input就变成了(i+1)th的buffer. 依次类推.

所以回答上面的问题, 我们当前level按照buffer/input的顺序传下去之后, 上来的时候buffer我们知道肯定是sorted的了, 那么input是什么状态呢? 其实就是sorted but one level. 也就是比buffer的sorted少了一个level的sorted(具体表现就是sorted的部分的range笑了一半).

看起来这个算法的改写是有点trivial, 不过偶尔这样深究一下recursion的思想方式还是很有意思的;

Problem Description

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]]
Difficulty:Medium
Total Accepted:25.4K
Total Submissions:45.8K
Contributor: LeetCode
Companies
google
Related Topics
greedy
Similar Questions
Count of Smaller Numbers After Self