2

メソッドは、ABS(a[i] - val) が k 個の最大の評価となるように、k 個の要素 a[i] を返す必要があります。私のコードは、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

トップ 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;
}

2 番目の方法: ヒープを使用して最大 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;
}

3 番目の方法: クイックソートのように、分割して征服します。配列を 2 つの部分に分割し、そのうちの 1 つで 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. (n - k) 番目の要素を探して、B で k-selection を実行します。O(n)予想時間アルゴリズムについては、Wikipedia のQuickselectを参照してください。
  3. 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
于 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 に答える