我有一个大小为1000的数组。如何找到五个最大元素的索引(索引)?
下面显示了带有设置代码的示例和我的尝试:
Random rand = new Random();
int[] myArray = new int[1000];
int[] maxIndices = new int[5];
int[] maxValues = new int[5];
for (int i = 0; i < myArray.length; i++) {
myArray[i] = rand.nextInt();
}
for (int i = 0; i < 5; i++) {
maxIndices[i] = i;
maxValues[i] = myArray[i];
}
for (int i = 0; i < maxIndices.length; i++) {
for (int j = 0; j < myArray.length; j++) {
if (myArray[j] > maxValues[i]) {
maxIndices[i] = j;
maxValues[i] = myArray[j];
}
}
}
for (int i = 0; i < maxIndices.length; i++) {
System.out.println("Index: " + maxIndices[i]);
}
我知道问题在于,它一直在向所有最大元素分配最高值。我不确定如何解决此问题,因为我必须保留的值和索引myArray
。
我不认为排序是一种选择,因为我需要保留索引。实际上,这是我特别需要的指标。
排序是一种选择,但要消耗额外的内存。考虑以下算法。
1. Allocate additional array and copy into - O(n)
2. Sort additional array - O(n lg n)
3. Lop off the top k elements (in this case 5) - O(n), since k could be up to n
4. Iterate over the original array - O(n)
4.a search the top k elements for to see if they contain the current element - O(lg n)
因此,步骤4是(n * lg n),就像排序一样。整个算法为n lg n,并且编码非常简单。
这是一个快速而肮脏的例子。其中可能存在错误,并且很明显空检查等开始起作用。
导入java.util.Arrays;
class ArrayTest {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
int[] indexes = indexesOfTopElements(arr,3);
for(int i = 0; i < indexes.length; i++) {
int index = indexes[i];
System.out.println(index + " " + arr[index]);
}
}
static int[] indexesOfTopElements(int[] orig, int nummax) {
int[] copy = Arrays.copyOf(orig,orig.length);
Arrays.sort(copy);
int[] honey = Arrays.copyOfRange(copy,copy.length - nummax, copy.length);
int[] result = new int[nummax];
int resultPos = 0;
for(int i = 0; i < orig.length; i++) {
int onTrial = orig[i];
int index = Arrays.binarySearch(honey,onTrial);
if(index < 0) continue;
result[resultPos++] = i;
}
return result;
}
}
您还可以采取其他措施来减少此操作的开销。例如,您可以选择使用仅跟踪最大5的队列来进行排序,而不是进行排序。作为队列,int
它们的值可能必须装箱才能添加到集合中(除非您自己滚动),这会大大增加开销。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句