我有一道算法题。
例如，有一个int[]数组，如[1,5,4,3,7,2]。
我想找到这个数组中第 k 个最大的差异，例如:
array[i] - array[j] = kth largest difference
(索引 i 必须小于 j 并且 array[i] 必须大于 array[j])。
输出是返回这个问题中的j。
我目前的想法:
- 我可以构建一个
int[][]来存储数组中的所有差异。 - 然后对它们进行排序，找到第 k 个最大的差异。
但是时间复杂度是O(n^2)。
有没有更好的解决方案？
最佳答案
您可以运行 2 个单独的方法来查找相应数组的最大值和最小值，然后找出差异。
或
您可以使用您的方法创建一个新数组，找出每个值的差异，然后找到该数组的最大值并输出。
然后使用 Array sort() 方法对数组重新排序并在 index+1 调用时打印出最大差值
关于java - 如何找到 int[] 中的第 K 个最大差异？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52096946/