返回未分类列表的n最高值的索引

Question

我已经编写了以下代码，现在正在尝试找出实现四个评论中解释的最佳方法：

    Integer[] expectedValues = new Integer[4];
    for (int i = 0; i <= 3; i++) {
        expectedValues[i] = getExpectedValue(i);
    }
    int choice = randomNumGenerator.nextInt(100) + 1;
    if (choice <= intelligence) {
        // return index of highest value in expectedValues
    } else if (choice <= intelligence * 2) {
        // return index of 2nd highest value in expectedValues
    } else if (choice <= intelligence * 3) {
        // return index of 3rd highest value in expectedValues
    } else {
        // return index of lowest value in expectedValues
    }

这样做的优雅方式是什么？我不需要将期望值保留为一个数组 - 我很乐意使用任何数据结构。

Answer 1

您可以创建一个包含索引的新数组并对值进行排序 - 在半伪码代码中，它看起来像这样(要适应(：

int[][] valueAndIndex = new int[n][2];
//fill array:
valueAndIndex[i][0] = i;
valueAndIndex[i][1] = expectedValues[i];
//sort on values in descending order
Arrays.sort(valueAndIndex, (a, b) -> Integer.compare(b[1], a[1]));
//find n-th index
int n = 3; //3rd largest number
int index = valueAndIndex[n - 1][0];

Answer 2

如果要使用简单数组，也许这可能是一个解决方案：

public static void main(String[] args) {
    int[] arr = new int[] { 1, 4, 2, 3 };
    int[] sorted = sortedCopy(arr);
    int choice = randomNumGenerator.nextInt(100) + 1;
    if (choice <= intelligence) {
        System.out.println(findIndex(arr, sorted[3])); // 1
    } else if (choice <= intelligence * 2) {
        System.out.println(findIndex(arr, sorted[2])); // 3
    } else if (choice <= intelligence * 3) {
        System.out.println(findIndex(arr, sorted[1])); // 2
    } else {
        System.out.println(findIndex(arr, sorted[0])); // 0
    }
}
static int[] sortedCopy(int[] arr) {
    int[] copy = new int[arr.length];
    System.arraycopy(arr, 0, copy, 0, arr.length);
    Arrays.sort(copy);
    return copy;
}
static int findIndex(int[] arr, int val) {
    int index = -1;
    for (int i = 0; i < arr.length; ++i) {
        if (arr[i] == val) {
            index = i;
            break;
        }
    }
    return index;
}

Answer 3

您可以"消除"最高值N-1次。之后，最高值是原始数组的n最高值：

public static void main(String[] args) {
    int[] numbers = new int[]{5, 9, 1, 4};
    int n = 2; // n-th index
    for (int i = 0; i < n - 1; ++i) {
        int maxIndex = findMaxIndex(numbers);
        numbers[maxIndex] = Integer.MIN_VALUE;
    }
    int maxIndex = findMaxIndex(numbers);
    System.out.println(maxIndex + " -> " + numbers[maxIndex]);
}
public static int findMaxIndex(int[] numbers) {
    int maxIndex = 0;
    for (int j = 1; j < numbers.length; ++j) {
        if (numbers[j] > numbers[maxIndex]) {
            maxIndex = j;
        }
    }
    return maxIndex;
}

复杂性是O(n * numbers.length)。