这是我的代码,用于查找数字数组中的最大数字,但我似乎无法理解如何获取前5个数字并将它们存储在数组中,然后检索它们
这是代码:
public class Max {
public static void main (String[] args)
{
int i;
int large[]=new int[5];
int array[] = {33,55,13,46,87,42,10,34,43,56};
int max = array[0]; // Assume array[0] to be the max for time-being
//Looping n-1 times, O(n)
for( i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
{
// O(1)
if( max < array[i])
{
// O(1)
max = array[i];// Change max if condition is True
large[i] = max;
}
}
for (int j = 0; j<5; j++)
{
System.out.println("Largest 5 : "+large[j]);
}
System.out.println("Largest is: "+ max);
// Time complexity being: O(n) * [O(1) + O(1)] = O(n)
}
}
我正在使用一个数组存储5个数字,但是当我运行它时,它不是我想要的.有人可以帮我解决这个问题吗？
Mar*_*nik 14
从较大的集合中检索前n项的最佳数据结构是最小/最大堆,相关的抽象数据结构称为优先级队列.Java有一个PriorityQueue基于堆结构的无界,但是没有专门用于基本类型的版本.它可以通过添加外部逻辑用作有界队列,有关详细信息,请参阅此注释.
Apache Lucene具有有界优先级队列的实现:
这是一个简单的修改,专门用于int:
/*
* Original work Copyright 2014 The Apache Software Foundation
* Modified work Copyright 2015 Marko Topolnik
*
* Licensed under the Apache License, Version 2.0 (the "License");
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/** A PriorityQueue maintains a partial ordering of its elements such that the
* worst element can always be found in constant time. Put()'s and pop()'s
* require log(size) time.
*/
class IntPriorityQueue {
private static int NO_ELEMENT = Integer.MIN_VALUE;
private int size;
private final int maxSize;
private final int[] heap;
IntPriorityQueue(int maxSize) {
this.heap = new int[maxSize == 0 ? 2 : maxSize + 1];
this.maxSize = maxSize;
}
private static boolean betterThan(int left, int right) {
return left > right;
}
/**
* Adds an int to a PriorityQueue in log(size) time.
* It returns the object (if any) that was
* dropped off the heap because it was full. This can be
* the given parameter (in case it isn't better than the
* full heap's minimum, and couldn't be added), or another
* object that was previously the worst value in the
* heap and now has been replaced by a better one, or null
* if the queue wasn't yet full with maxSize elements.
*/
public void consider(int element) {
if (size < maxSize) {
size++;
heap[size] = element;
upHeap();
} else if (size > 0 && betterThan(element, heap[1])) {
heap[1] = element;
downHeap();
}
}
public int head() {
return size > 0 ? heap[1] : NO_ELEMENT;
}
/** Removes and returns the least element of the PriorityQueue in log(size)
time. */
public int pop() {
if (size > 0) {
int result = heap[1];
heap[1] = heap[size];
size--;
downHeap();
return result;
} else {
return NO_ELEMENT;
}
}
public int size() {
return size;
}
public void clear() {
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
private void upHeap() {
int i = size;
// save bottom node
int node = heap[i];
int j = i >>> 1;
while (j > 0 && betterThan(heap[j], node)) {
// shift parents down
heap[i] = heap[j];
i = j;
j >>>= 1;
}
// install saved node
heap[i] = node;
}
private void downHeap() {
int i = 1;
// save top node
int node = heap[i];
// find worse child
int j = i << 1;
int k = j + 1;
if (k <= size && betterThan(heap[j], heap[k])) {
j = k;
}
while (j <= size && betterThan(node, heap[j])) {
// shift up child
heap[i] = heap[j];
i = j;
j = i << 1;
k = j + 1;
if (k <= size && betterThan(heap[j], heap[k])) {
j = k;
}
}
// install saved node
heap[i] = node;
}
}
您实现的方式betterThan决定它是表现为最小还是最大堆.这就是它的用法:
public int[] maxN(int[] input, int n) {
final int[] output = new int[n];
final IntPriorityQueue q = new IntPriorityQueue(output.length);
for (int i : input) {
q.consider(i);
}
// Extract items from heap in sort order
for (int i = output.length - 1; i >= 0; i--) {
output[i] = q.pop();
}
return output;
}
对于这种方法的性能与用户rakeb.void的简单线性扫描表达了一些兴趣.这些是size与输入大小有关的结果,总是寻找16个顶级元素:
Benchmark (size) Mode Cnt Score Error Units
MeasureMinMax.heap 32 avgt 5 270.056 ± 37.948 ns/op
MeasureMinMax.heap 64 avgt 5 379.832 ± 44.703 ns/op
MeasureMinMax.heap 128 avgt 5 543.522 ± 52.970 ns/op
MeasureMinMax.heap 4096 avgt 5 4548.352 ± 208.768 ns/op
MeasureMinMax.linear 32 avgt 5 188.711 ± 27.085 ns/op
MeasureMinMax.linear 64 avgt 5 333.586 ± 18.955 ns/op
MeasureMinMax.linear 128 avgt 5 677.692 ± 163.470 ns/op
MeasureMinMax.linear 4096 avgt 5 18290.981 ± 5783.255 ns/op
结论:针对堆方法的常数因素非常低.盈亏平衡点大约是70-80个输入元素,从那时起,简单的方法就会急剧下降.请注意,常量因子源于按排序顺序提取项目的最终操作.如果不需要这样(即,只有一组最佳项就足够了),我们可以直接检索内部heap数组并忽略heap[0]算法未使用的元素.在这种情况下,即使对于最小的输入大小,这个解决方案也会像rakib.void一样胜出(我测试了32个中的4个顶部元素).
看下面的代码:
public static void main(String args[]) {
int i;
int large[] = new int[5];
int array[] = { 33, 55, 13, 46, 87, 42, 10, 34, 43, 56 };
int max = 0, index;
for (int j = 0; j < 5; j++) {
max = array[0];
index = 0;
for (i = 1; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
index = i;
}
}
large[j] = max;
array[index] = Integer.MIN_VALUE;
System.out.println("Largest " + j + " : " + large[j]);
}
}
注意:如果您不想更改输入的数组,请复制它并对复制的数组执行相同的操作.
我得到以下输出:
最大的0:87
最大的1:56
最大的2:55
最大的3:46
最大的4:43