2021-08-26:长度为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小的数值对。
福大大 答案2021-08-26:
1.暴力解。
时间复杂度:(N^2 * log(N^2)).
2.下标定位+bfprt算法。
2.1.k--。...2.2.定位下标i1和i2。
i1=k/N。
i2=k%N。
2.3.根据bfprt算法求出第i1小和第i2小的数。
时间复杂度:O(N)。
空间复杂度:O(1)。arr数组里的元素顺序会发生变化。