算法之 — 求二维数组最大n个数 - litonghui/TechBlog GitHub Wiki

最近看到某公司一道算法面试题，题目是一个m*n的二维数组matrix中，找到最大k个数。

分析题目，考查知识点是对多维数据的查找和排序，不要被二维数组这个概念给带偏了，对于二维数组我们一贯的认知就是一位数组简单分割。需要注意的是二维数组 matrix 在使用前需要对matrix.length 和 matrix[0].length 判断。

解法一：

对数组降维，new 一个 m*n 的一维数组matrix_s ，存储二维数组matrix 的所有数值，通过对一维数组降序排序（快排，堆排等），取前k个数，即所需要。时间复杂度和空间复杂度相比而言比较大，对于较大的二维数组，不是最优解法。

解法二：

采取DP算法思想，new 一个 k的 一维数组matrix_s ，遍历二维数组matrix,给一维数组matrix_s赋值，直到matrix_s 数组被赋满值，此时一维数组matrix_s 进行降序排序（快排，堆排等），至于后面的二维数组 m*n-k个数插入matrix_s数组中 ,插入时只需判断，matrix[i][j] > matrix_s[k-1]才允许插入，当然保证matrix_s 数组降序，采用尾部遍历，插入适当位置。

代码分析：

public int[] findMaxArray(int [][] matrix,int k) {
    if (matrix.length == 0 || k == 0)
        return new int[0];
    int[] arr = new int[k];
    int x = 0;
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[i].length; j++) {
            if (x < k) {
                arr[x] = matrix[i][j];
                x++;
                if (x == k) {
                    sortArr(arr);
                }
            } else {
                insertSort(arr,matrix[i][j]);
            }
        }
    return arr;
}

快速排序对一维数组，保证降序

public int[] sortArr(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
    return arr;
}
public void quickSort(int[] arr,int left,int right) {
    if (left >= right)
        return;
    int low = left, heigth = right;
    int k = arr[left];
    while (left < right) {
        while (left < right && arr[right] < k)
            right--;
        arr[left++] = arr[right];
        while (left < right && arr[left] > k)
            left++;
        arr[right--] = arr[left];
    }
    arr[left] = k;
    quickSort(arr, low, left - 1);
    quickSort(arr, right + 1, heigth);
}

倒叙插入降序数组，采用动态规划方式，选取始终大于当前数组最小的元素插入。

public void insertSort(int []arr,int num) {
    if (arr[arr.length - 1] > num)
        return;
    int i;
    for (i = arr.length - 1; i > 0; i--) {
        if (arr[i - 1] < num) {
            arr[i] = arr[i - 1];
        } else {
            break;
        }
    }
    arr[i] = num;
}

测试一下设计是否正确（Android log 方式）：

    int[][] matrix = {{4, 12, 13}, {1, 45, 7}, {8, 9, 12}, {0, 6, 11}};
    int [] max = findMaxArray(matrix,8);
    StringBuilder builder = new StringBuilder();
    for (int m:max){
        builder.append(m).append(",");
    }
    Log.v("lth","max:"+builder);