给定数组arr和整数k，返回第k小的数值对的解法

问题描述

        长度为N的数组arr，一定可以组成N^2个数值对。
        例如arr = [3,1,2]，数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)，也就是任意两个数都有数值对，而且自己和自己也算数值对。
        数值对怎么排序？规定，第一维数据从小到大，第一维数据一样的，第二维数组也从小到大。所以上面的数值对排序的结果为：(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
        给定一个数组arr，和整数k，返回第k小的数值对。

思路

        假设数组有序，数组的长度为n，那么第 k 小的数值对的第一元素在原素组的下标其实可以算出来是 f=(k-1)/n 。我们重新遍历数组可以计算出小于下标 f 的数有 a 个，等于下标 f 的数有 b 个。此时我们我们分析可知在数值对中第一个元素下标为 f 之前共有 a*n个，即此时问题转化为我们需要在数值对找到第一个元素下标为 f 的第  (k -a*n)=s 个元素。小于下标 f 的元素每个都有 b 次出现，我们就可以计算出数值对中第二个元素的下标为 (s-1)/b。

        此题已知的数组并不是一个有序数组，我们需要进行排序。在排序算法中最好的时间复杂度也是O(N*logN)。但是我们重新分析题会发现我们并不是需要数组全部排序，我们只是需要知道在无序数组中的第i小的数字是什么即可（快排改进）。根据这一需求我们可以进行优化，把原本O(N*logN)的时间复杂度降为O(N)。

代码

 方案一：首先定义一个类Pair，使用暴力递归的方式解题，最后使用系统提供的方法进行排序。

        该方法的时间复杂度为 O(N^2*log(N^2))。

​    public static class Pair {
        public int x;
        public int y;
 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static class PairComparator implements Comparator {
 
        @Override
        public int compare(Pair o1, Pair o2) {
            return o1.x != o2.x ? o1.x - o2.x : o1.y - o2.y;
        }
    }
 
​
    public static int[] kthMinPair1(int[] arr, int k) {
        int N = arr.length;
        if (k > N * N) {
            return null;
        }
        Pair[] pairs = new Pair[N * N];
        int index = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                pairs[index++] = new Pair(arr[i], arr[j]);
            }
        }
        Arrays.sort(pairs, new PairComparator());
        return new int[]{pairs[k - 1].x, pairs[k - 1].y};
    }

方案二：按照上面思路中的第一段思想进行解题。

        时间复杂度为O(N*logN)。

    public static int[] kthMinPair2(int[] arr, int k) {
        int N = arr.length;
        if (k > N * N) {
            return null;
        }
        //O(N*logN)
        Arrays.sort(arr);
        //第k小的数值对，第一位数字
        int firstNum = arr[(k - 1) / N];
        int lessFirstNumSize = 0;//数出比firstNum小的数有几个
        int firstNumSize = 0;//数组中==firstNum的数有几个
        //<= firstNum
        for (int i = 0; i < N && arr[i] <= firstNum; i++) {
            if (arr[i] < firstNum) {
                lessFirstNumSize++;
            } else {
                firstNumSize++;
            }
        }
        int rest = k - (lessFirstNumSize * N);
        return new int[]{firstNum, arr[(rest - 1) / firstNumSize]};
    }

方案三：按照思路中第二段思想，即改写快排，实现在无序数组中查找第index小的数字。

        时间复杂度为O(N)。

    public static int getMinKth(int[] arr, int index) {
        int L = 0;
        int R = arr.length - 1;
        int pivot = 0;
        int[] range = null;
        while (L < R) {
            pivot = arr[L + (int) (Math.random() * (R - L + 1))];
            range = partition(arr, L, R, pivot);
            if (index < range[0]) {
                R = range[0] - 1;
            } else if (index > range[1]) {
                L = range[1] + 1;
            } else {
                return pivot;
            }
        }
        return arr[L];
    }
 
    public static int[] partition(int[] arr, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, cur, --more);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
 
    public static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }