1

需要返回 k 个元素 a[i] 使得 ABS(a[i] - val) 是 k 个最大的评估。我的代码仅适用于大于 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

通过将距离存储为绝对值，您会破坏最后一个 for 循环，该循环会从 abs 值重新计算原始值。

如何使用一个比较器，该比较器使用 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] - val)

这是您的排序标准，因此您需要实现一个比较器，将其应用于要比较的两个值，并返回两个结果值的比较结果。

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 回答