二维数组的排序


已知一个M行N列的二维数组,数组的每一列都已经排好序,行是无序的,将二维数组转化为一维数组,使一维数组中的元素按照从小到的的顺序排列,要求算法的复杂度最低(请给出代码)。
例如:R = [[1.1, 3.31, 2.21, 5.5, 4.4],
[2.2, 4.41, 3.32, 6.6, 5.5],
[3.3, 5.51, 4.42, 6.61, 6.62],
[4.42, 6.63, 5.52, 6.64, 7.1]]
result = [1.1, 2.2, 2.21, ..., 7.1]
已邀请:

寒老师

赞同来自:


可视作n个有序数组合并的问题。
猜测面试官是基于分布式系统中合并数据设计的题目,有时候确实需要处理不同客户端的排序好的数组/链表,合并到主服务器上。
这也是leetcode中的题目,似乎有2种标准做法,我搬运一下。

1)类似于MergeSort的思路,进行分治处理。先把k个list分成两半,然后继续划分,直到剩下两个list就合并起来,合并时会用到类似 Merge Two Sorted Lists 这道题的思路。 这种思路我们分析一下复杂度,如果有k个list,每个list最大长度是n,那么我们就有分治思路的复杂度计算公式 T(k) = 2T(k/2) O(n*k)。 其中T(k)表示k个list合并的时间复杂度,用主定理可以算出时间复杂度是O(nklogk)。

2)运用堆。我们维护一个大小为k的堆,先把每个list的第一个元素放入堆之中,然后每次从堆顶选取最小元素放入结果最后的list里面,然后读取该元素所在list的下一个元素放入堆中,重新维护好堆,然后重复这个过程。因为每个链表/数组是有序的,每次又是取当前k个元素中最小的,所以最后结果的list的元素是按从小到大顺序排列的。这种方法的时间复杂度也是O(nklogk)。

顺便搬运一下第2种方法的动态图和代码
public class MergeKSortedArrays {

    public int size;
    public HeapNode[] Heap;
    public int position;
    int[] result;

    public MergeKSortedArrays(int k) {
        this.size = k;
        Heap = new HeapNode[k + 1]; // size+1 because index 0 will be empty
        position = 0;
        Heap[0] = new HeapNode(0, -1); // put some junk values at 0th index node
    }

    public int[] merge(int[][] A, int k, int n) {
        int nk = n * k;
        result = new int[nk];
        int count = 0;
        int[] ptrs = new int[k];
        // create index pointer for every list.
        for (int i = 0; i < ptrs.length; i++) {
            ptrs[i] = 0;
        }
        for (int i = 0; i < k; i++) {
            if (ptrs[i] < n) {
                insert(A[i][ptrs[i]], i); // insert the element into heap
            } else {
                insert(Integer.MAX_VALUE, i); // if any of this list burns out, insert +infinity
            }

        }
        while (count < nk) {
            HeapNode h = extractMin(); // get the min node from the heap.
            result[count] = h.data; // store node data into result array
            ptrs[h.listNo]++; // increase the particular list pointer
            if (ptrs[h.listNo] < n) { // check if list is not burns out
                insert(A[h.listNo][ptrs[h.listNo]], h.listNo); // insert the next element from the list
            } else {
                insert(Integer.MAX_VALUE, h.listNo); // if any of this list burns out, insert +infinity
            }
            count++;
        }
        return result;
    }

    public void insert(int data, int listNo) {
        if (position == 0) { // check if Heap is empty
            Heap[position + 1] = new HeapNode(data, listNo); // insert the first element in heap
            position = 2;
        } else {
            Heap[position++] = new HeapNode(data, listNo);// insert the element to the end
            bubbleUp(); // call the bubble up operation
        }
    }

    public HeapNode extractMin() {
        HeapNode min = Heap[1]; // extract the root
        Heap[1] = Heap[position - 1]; // replace the root with the last element in the heap
        Heap[position - 1] = null; // set the last Node as NULL
        position--; // reduce the position pointer
        sinkDown(1); // sink down the root to its correct position
        return min;
    }

    public void sinkDown(int k) {
        int smallest = k;
        // check which is smaller child , 2k or 2k+1.
        if (2 * k < position && Heap[smallest].data > Heap[2 * k].data) {
            smallest = 2 * k;
        }
        if (2 * k + 1 < position && Heap[smallest].data > Heap[2 * k + 1].data) {
            smallest = 2 * k + 1;
        }
        if (smallest != k) { // if any if the child is small, swap
            swap(k, smallest);
            sinkDown(smallest); // call recursively
        }

    }

    public void swap(int a, int b) {
        // System.out.println("swappinh" + mH[a] + " and " + mH[b]);
        HeapNode temp = Heap[a];
        Heap[a] = Heap[b];
        Heap[b] = temp;
    }

    public void bubbleUp() {
        int pos = position - 1; // last position
        while (pos > 0 && Heap[pos / 2].data > Heap[pos].data) { // check if its parent is greater.
            HeapNode y = Heap[pos]; // if yes, then swap
            Heap[pos] = Heap[pos / 2];
            Heap[pos / 2] = y;
            pos = pos / 2; // make pos to its parent for next iteration.
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] A = new int[5][];
        A[0] = new int[] { 1, 5, 8, 9 };
        A[1] = new int[] { 2, 3, 7, 10 };
        A[2] = new int[] { 4, 6, 11, 15 };
        A[3] = new int[] { 9, 14, 16, 19 };
        A[4] = new int[] { 2, 4, 6, 9 };
        MergeKSortedArrays m = new MergeKSortedArrays(A.length);
        int[] op = m.merge(A, A.length, A[0].length);
        System.out.println(Arrays.toString(op));
    }

}

// Every Node will store the data and the list no from which it belongs
class HeapNode {
    int data;
    int listNo;

    public HeapNode(int data, int listNo) {
        this.data = data;
        this.listNo = listNo;
    }
}

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~