长度为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小的数值对

what?就这么so easy的题。不就是列出所有的组合，然后比较对这些组合进行排序吗，这不是轻轻松松搞定面试官？搞定全宇宙吗？来让他们见识一下真正的技术吧。。。。

Talk is cheap. Show me the code.于是乎风骚的代码正式上线，

package com.edward.demo; import java.util.Arrays;import java.util.Comparator; //数值对public class Calculate {    public static  class PairArr{        public int first;        public int second;         public PairArr(int first, int second) {            this.first = first;            this.second = second;        }    }     public static class PairArrCompare implements Comparator<PairArr>{        @Override        public int compare(PairArr o1, PairArr o2) {            return o1.first != o2.first ? o1.first - o2.first : o1.second - o2.second;        }    }     public static int[] findKMinPair(int[] resources, int k){        int length = resources.length;        if( k > length * length){            return null;        }        PairArr[] pairArrs = new PairArr[length * length];        int index = 0;        for (int i = 0; i < length; i++) {            for (int j = 0; j < length; j++) {                pairArrs[index ++] = new PairArr(resources[i],resources[j]);            }        }        Arrays.sort(pairArrs,new PairArrCompare());        return new int[]{pairArrs[k - 1].first,pairArrs[k-1].second};    }        public static void main(String[] args) {        int[] resources = {1, 1, 2, 2, 2, 3,3};        int k = 21;        System.out.println(Arrays.toString(findKMinPair(resources,k)));    } }

区区几十行代码速度解决战斗，运行的demo也很丝滑，没有一点犹豫的就执行出来了，这精简而又通俗易懂的程度，往低了说也得99吧！！！信心慢慢的提交了答卷。面试官的反应

上面代码的复杂度：面试官会给你一个O（N^2log（N^2））

方法二：

我们再来分析一下整体的数组：例如{1, 2, 3}，以下是所有的情况罗列

再举个例子{1, 1, 2, 2, 2, 3, 3}，罗列所有的组合：

第一个数字是1与数组{1, 1, 2, 2, 2, 3, 3}匹配，获取所有的数字对是【1，数组所有的数字】

第二个数字是1与数组{1, 1, 2, 2, 2, 3, 3}匹配，获取所有的数字对是【1，数组所有的数字】.......

所以我们可以很轻松的获取到数值对的第一位数字：arr[（K -1 ）/数组的长度]

第二位数字怎么获取呢？？？？

还是arr = {1, 1, 2, 2, 2, 3, 3}这个数组，如果去第21小的数字对，我们可以轻松的获取到第一位数字：arr[（21 -1）/ 7] = arr[2] = 2 ，第一位是2

所有的数值对是从小大排列，arr有3个数字2，那么就会有 {2,2,2} 分别于{1, 1, 2, 2, 2, 3, 3}组成的组合，那么第二位的数字我们就呼之欲出了，arr[ (21 - 小于2数字的个数 * 7 - 1) / 3] = arr [( 21 - 2 * 7 - 1) /3]=arr[2] = 2;最后的结果就是 {arr[2],arr[2]} ={2,2}

show me the code

public static int[] findKMinPair2(int[] resources, int k){        int length = resources.length;        if( k > length * length){            return null;        }        Arrays.sort(resources);        //找出第一位数字        int firstNum = resources[(k - 1)/ length];         //小于firstNum的个数        int lessFirstNumSize = 0;        //找出等于firstNum的个数        int firstNumSize = 0;        for (int i = 0; i < length && resources[i] <= firstNum; i++) {            if(resources[i] < firstNum){                lessFirstNumSize++;            }else {                firstNumSize++;            }        }        int restK = k - (lessFirstNumSize * length);        return new int[]{firstNum,resources[(restK - 1) / firstNumSize]};    }

搞定，骚年你是不是感觉到这已经结束了？？？no no no, 骚年 too young too simple，你还是不太了解面试官

方法二天然的需要排序，如果是无需呢？这个问题就换成了，在一个无序的数组中获取到第K小的数据，是不是有点熟悉，这就是TOP-K问题，，大名鼎鼎的BFPTR算法（也叫中位数的中位数算法），该算法可以从一堆无序数字中拿出第k小的数字，而且，而且最神奇的是！！！该算法在最坏情况下的时间复杂度竟然只有O(N)

public static int[] findKMinPair2(int[] resources, int k){        int length = resources.length;        if( k > length * length){            return null;        }        Arrays.sort(resources);        //找出第一位数字        int firstNum = bfptr(resources,0,length - 1,(k -1 )/ length + 1);         //小于firstNum的个数        int lessFirstNumSize = 0;        //找出等于firstNum的个数        int firstNumSize = 0;        for (int i = 0; i < length && resources[i] <= firstNum; i++) {            if(resources[i] < firstNum){                lessFirstNumSize++;            }else {                firstNumSize++;            }        }        int restK = k - (lessFirstNumSize * length);        int second = bfptr(resources,0,length - 1,(restK - 1) / firstNumSize + 1);         return new int[]{firstNum,second};    }     public static void main(String[] args) {        int[] resources = {1, 1, 2, 2, 2, 3, 3};        int k = 21;        System.out.println(Arrays.toString(findKMinPair2(resources,k)));    }     public static int findMid(int[] arr,int l,int r){        if (l == r) return arr[l];        int i;        int n = 0;        for(i = l; i < r - 5; i += 5){            insertSort(arr, i, i + 4);            n = i - l;            swap(arr,l + n / 5, i + 2);        }         //处理剩余元素        int num = r - i + 1;        if(num > 0){            insertSort(arr, i, i + num - 1);            n = i - l;            swap(arr,l + n / 5, i + num / 2);        }        n /= 5;        if(n == l) return arr[l];        return findMid(arr, l, l + n);    }     public static int findMidIndex(int[] arr,int l,int r,int num){        for (int i = l; i <= r; i++) {            if (arr[i] == num) return i;        }        return -1;    }     public static int Partition(int[] arr, int l, int r, int p){        swap(arr,p, l);        int i = l;        int j = r;        int pivot = arr[l];        while(i < j){            while(arr[j] >= pivot && i < j)                j--;            arr[i] = arr[j];            while(arr[i] <= pivot && i < j)                i++;            arr[j] = arr[i];        }        arr[i] = pivot;        return i;    }     //插入排序    public static void insertSort(int[] arr,int l,int r){        for (int i = l + 1; i <= r; i++) {            if (arr[i - 1] > arr[i]) {                int t = arr[i];                int j = i;                while (j > l && arr[j - 1] > t) {                    arr[j] = arr[j - 1];                    j--;                }                arr[j] = t;            }        }    }    //数组元素交换    public static void swap(int[] arr,int i,int j){        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }     public static int bfptr(int[] arr,int l,int r,int k){        int num = findMid(arr, l, r);    //寻找中位数的中位数        int p =  findMidIndex(arr, l, r, num); //找到中位数的中位数对应的index        int i = Partition(arr, l, r, p);         int m = i - l + 1;        if(m == k) return arr[i];        if(m > k)  return bfptr(arr, l, i - 1, k);        return bfptr(arr, i + 1, r, k - m);    }

骚年 想知道更多的套路吗？欢迎关注：叮铛的公众号，套路三联。。。。。。

欢迎关注作者公众号交流:技术小叮铛！！！！技术小叮铛！！！！！

私信+留言+关注+转发可以可以免费领取一份大厂面试题