1

ABS(a[i] - val) が k 個の最大の評価となるように、k 個の要素 a[i] を返す必要があります。私のコードは、val より大きい整数に対してのみ機能します。val より小さい整数の場合は失敗します。java.util.Arrays 以外のものをインポートせずにこれを行うことはできますか? どんな助けでも大歓迎です！

import java.util.Arrays;

public final class Selector {

private Selector() {
 } 
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;    
}

テストケース：

import org.junit.Assert;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;


public class SelectorTest {


 /** Fixture initialization (common initialization
  *  for all tests). **/
 @Before public void setUp() {
 }
  @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:<13>
 FAILURES!!!
 Tests run: 1,  Failures: 1
4

2 に答える 2

1

距離を絶対値として保存することで、abs-value から元の値を再計算する最後の for ループを破棄します。

比較のために abs 値を使用しているが、配列 b に検索値からの配列値の差を格納しているコンパレーターを使用するのはどうですか?

これは次のようになります。

public static int[] farthestK(int[] a, int val, int k) {// This line should not change
    Integer[] b = new Integer[a.length];
    for (int i = 0; i < b.length; i++) {
      b[i] = a[i] - val;
    }
    Arrays.sort(b, new Comparator<Integer>() {

      @Override
      public int compare(Integer arg0, Integer arg1) {
        return Integer.valueOf(Math.abs(arg0)).compareTo(Math.abs(arg1));
      }
    });
    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;
  }
于 2013-09-04T06:10:45.577 に答える
0

ABS(a[i] - 値)

これはソート基準であるため、比較する 2 つの値にそれを適用し、結果の 2 つの値の比較結果を返すComparatorを実装する必要があります。

public static int[] farthestK(int[] a, int val, int k) {
    // copy into an array of non primitive integers 
    // for using in the sort method
    Integer[] b = new Integer[a.length];
    for(int i = 0; i < a.length; i++) {
        b[i] = a[i];
    }

    final int v = val; // make val final for access in anonymous class
    Arrays.sort(b, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            int v1 = Math.abs(o1.intValue() - v);
            int v2 = Math.abs(o2.intValue() - v);
            return - (v1 - v2); // return inverted result of comparison
                                // for convenient copying later
                                // or just (v2 - v1)
        }
    });

    // copy first k elements
    int[] c = new int[k];
    for(int i = 0; i < k; i++) {
        c[i] = b[i];
    }
    return c;
}

上記のコードは もインポートすることに注意してくださいjava.util.Comparator。インポートが許可されていない場合、数値を数値順にソートしたくないため、メソッドArrays.sort(T[] a)はニーズに適合しません。その場合、独自の並べ替えアルゴリズムを実装し、上記と同じ比較ロジックを使用する必要があります。

以下は、 int 配列の単純なマージソートを使用した実装です。

public static int[] farthestK(int[] a, int val, int k) {
    return Arrays.copyOf(sort(a, val), k);
}

private static int compare(int o1, int o2, int v) {
    int v1 = Math.abs(o1 - v);
    int v2 = Math.abs(o2 - v);
    return (v2 - v1);
}

private static int[] sort(int[] a, int v) {
    return mergesort(a, v);
}

private static int[] mergesort(int[] a, int v) {
    if(a.length <= 1) {
        return a;
    }
    int m = a.length / 2;
    int[] la = mergesort(Arrays.copyOfRange(a, 0, m), v);
    int[] ra = mergesort(Arrays.copyOfRange(a, m, a.length), v);
    return merge(la, ra, v);
}

private static int[] merge(int[] la, int[] ra, int v) {
    int[] a = new int[la.length + ra.length];
    int il = 0, ir = 0, ia = 0;
    while(il < la.length && ir < ra.length) {
        if(compare(la[il], ra[ir], v) <= 0) {
            a[ia++] = la[il++];
        } else {
            a[ia++] = ra[ir++];
        }
    }
    while(il < la.length) {
        a[ia++] = la[il++];
    }
    while(ir < ra.length) {
        a[ia++] = ra[ir++];
    }
    return a;
}

基本的に、すべてのコピーを自分で行うことも、 Arraysのインポートを取り除くこともできます。

また、実際には、mersort の左右の配列すべてをすべてコピーする必要はないことに注意してください。必要なのは、元の配列と同じ長さの単一の新しい配列であり、開始/終了インデックスを操作して左右の配列を識別します。

于 2013-09-04T06:38:24.233 に答える