2

方法需要返回 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
4

4 回答 4

3

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) 代码有点长，这里只提供链接。

选择问题。

于 2013-09-04T03:34:03.637 回答
2

对数组进行排序将花费您O(n log n)时间。您可以使用 k 选择在O(n)时间内完成。

  1. 计算一个数组 B，其中 B[i] = abs(A[i] - val)。那么你的问题就相当于在 B 中找到离零最远的 k 个值。由于每个 B[i] >= 0，这相当于在 B 中找到 k 个最大元素。
  2. 在 B 上运行 k-selection，寻找第 (n - k) 个元素。请参阅Wikipedia 上的Quickselect了解 O(n)预期时间算法。
  3. k-selection 完成后，B[n - k] 到 B[n - 1] 包含 B 中最大的元素。通过适当的簿记，您可以链接回 A 中与它们对应的元素（参见下面的伪代码）。

时间复杂度：#1 为 O(n) 时间，#2 为 O(n) 时间，#3 为 O(k) 时间 => 总时间复杂度为O(n). （快速选择在 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
于 2013-09-04T03:57:45.710 回答
0

您可以稍微修改此算法，并根据您的要求将其用于打印 k 个元素。（这是您需要对该算法进行一些更改的唯一工作。）

探索此链接。 http://jakharmania.blogspot.in/2013/08/selection-of-kth-largest-element-java.html

该算法使用选择排序 - 因此输出将是一个非常有效的基于对数时间复杂度的答案。

于 2013-09-04T03:26:03.687 回答
0

O(n)算法，来自关于部分排序的维基百科条目：

使用线性时间中位数选择算法找到第 k 个最小的元素。然后进行一次线性遍历以选择小于第 k 个最小元素的元素。

在这种情况下，集合是通过获取原始数组、减去给定值、获取绝对值（然后将其取反以使最大变为最小）来创建的。

于 2013-09-04T04:07:00.420 回答