方法需要返回k个元素a[i]，以便ABS（a[i]-val）是k个最大的求值。我的代码只适用于大于val的整数。如果整数小于val，它就会失败。我可以在不导入java.util.Arrays之外的任何东西的情况下完成这项工作吗？有人能启发我一下吗？任何帮助都将不胜感激！
public static int[] farthestK(int[] a, int val, int k) {// This line should not change
int[] b = new int[a.length];
for (int i = 0; i < b.length; i++) {
b[i] = Math.abs(a[i] - val);
}
Arrays.sort(b);
int[] c = new int[k];
int w = 0;
for (int i = b.length-1; i > b.length-k-1; i--) {
c[w] = b[i] + val;
w++;
}
return c;
}
测试用例：
@Test public void farthestKTest() {
int[] a = {-2, 4, -6, 7, 8, 13, 15};
int[] expected = {15, -6, 13, -2};
int[] actual = Selector.farthestK(a, 4, 4);
Assert.assertArrayEquals(expected, actual);
}
There was 1 failure:
1) farthestKTest(SelectorTest)
arrays first differed at element [1]; expected:<-6> but was:<14>
FAILURES!!!
Tests run: 1, Failures: 1
top k问题可以通过多种方式解决。在您的情况下，您添加了一个新参数，但这并不重要。
第一个也是最简单的一个：只需对数组进行排序。时间复杂度：O（nlogn）
public static int[] farthestK(Integer[] a, final int val, int k) {
Arrays.sort(a, new java.util.Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return -Math.abs(o1 - val) + Math.abs(o2 - val);
}
});
int[] c = new int[k];
for (int i = 0; i < k; i++) {
c[i] = a[i];
}
return c;
}
第二种方法：使用堆保存最大k值，时间复杂度：O（nlogk）
/**
* Use a min heap to save the max k values. Time complexity: O(nlogk)
*/
public static int[] farthestKWithHeap(Integer[] a, final int val, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(4,
new java.util.Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Math.abs(o1 - val) - Math.abs(o2 - val);
}
});
for (int i : a) {
minHeap.add(i);
if (minHeap.size() > k) {
minHeap.poll();
}
}
int[] c = new int[k];
for (int i = 0; i < k; i++) {
c[i] = minHeap.poll();
}
return c;
}
第三种方式：分而治之，就像快速排序一样。将数组划分为两部分，并在其中一部分中找到第k个。时间复杂度：O（n+klogk）代码有点长，所以我只是在这里提供链接。
选择问题。
对数组进行排序将花费O（n log n）时间。您可以使用k选择在O（n）时间内完成。
- 计算一个数组B，其中B[i]=abs（A[i]-val）。那么你的问题就等价于在B中找到离零最远的k个值。由于每个B[i]>=0，这就等价于找到B中最大的k个元素
- 在B上运行k选择，查找第（n-k）个元素。有关O（n）预期时间算法，请参阅维基百科上的Quickselect
- 在k选择完成后，B[n-k]到B[n-1]包含B中最大的元素。通过正确的记账，您可以链接回A中与它们对应的元素（见下面的伪代码）
时间复杂度：#1的O（n）时间、#2的O（n）时间和#3的O（k）时间=>O(n)的总时间复杂度。（Quickselect在O（n）预期时间内运行，存在复杂的最坏情况线性时间选择算法）。
空间复杂度：O(n)。
伪码：
farthest_from(k, val, A):
let n = A.length
# Compute B. Elements are objects to
# keep track of the original element in A.
let B = array[0 .. n - 1]
for i between 0 and n - 1:
B[i] = {
value: abs(A[i] - val)
index: i
}
# k_selection should know to compare
# elements in B by their "value";
# e.g., each B[i] could be java.lang.Comparable.
k_selection(n - k - 1, B)
# Use the top elements in B to link back to A.
# Return the result.
let C = array[0 .. k - 1]
for i between 0 and k - 1:
C[i] = A[B[n - k + i].index]
return C
您可以稍微修改此算法，并根据您的要求将其用于打印k个元素。（这是您需要对该算法进行一些更改的唯一工作。）
浏览此链接http://jakharmania.blogspot.in/2013/08/selection-of-kth-largest-element-java.html
该算法使用选择排序，因此输出将是基于对数时间复杂性的答案，这是非常有效的。
O(n)算法，来自维基百科关于部分排序的条目：
使用中位数的线性时间中位数选择算法找到第k个最小元素。然后进行线性传递以选择小于第k个最小元素的元素。
在这种情况下，集合是通过取原始数组，减去给定值，取绝对值来创建的（然后将其取反，使最大值变为最小值）。