Java 没有排序的 10 个数字数组中最大的 5 个

Largest 5 in array of 10 numbers without sorting

提问by bappi bazzi

Here's my code to find the max number in an array of numbers, but i can't seem to understand how to get the top 5 numbers and store them in an array and later retrieve them

这是我在数字数组中查找最大数字的代码，但我似乎无法理解如何获取前 5 个数字并将它们存储在一个数组中，然后再检索它们

Here's the code:

这是代码：

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)
    }

}

I'm using an array to store 5 numbers, but when i run it, it is not what i want. Can anyone help me with the program?

我正在使用一个数组来存储 5 个数字，但是当我运行它时，这不是我想要的。任何人都可以帮助我完成程序吗？

采纳答案by rakeb.mazharul

Look at the following code:

看下面的代码：

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]);
    }
}

Note:If you don't want to change the inputted array, then make a copy of it and do the same operation on the copied array.

注意：如果您不想更改输入的数组，请复制它并在复制的数组上执行相同的操作。

Take a look at Integer.MIN_VALUE.

看看Integer.MIN_VALUE。

I get the following output:

我得到以下输出：

Largest 0 : 87

Largest 1 : 56

Largest 2 : 55

Largest 3 : 46

Largest 4 : 43

最大的 0 : 87

最大 1 : 56

最大的 2 : 55

最大 3 : 46

最大 4 : 43

回答by Marko Topolnik

The optimum data structure to retrieve top n items from a larger collection is the min/max heapand the related abstract data structure is called the priority queue. Java has an unbounded PriorityQueuewhich is based on the heap structure, but there is no version specialized for primitive types. It can used as a bounded queue by adding external logic, see this commentfor details..

从较大的集合中检索前 n 项的最佳数据结构是最小/最大堆，相关的抽象数据结构称为优先级队列。Java 有一个PriorityQueue基于堆结构的 unbounded ，但没有专门用于原始类型的版本。它可以通过添加外部逻辑用作有界队列，详情请参阅此注释。

Apache Lucene has an implementation of the bounded priority queue:

Apache Lucene 有一个有界优先队列的实现：

http://grepcode.com/file/repo1.maven.org/maven2/org.apache.lucene/lucene-core/5.2.0/org/apache/lucene/util/PriorityQueue.java#PriorityQueue

http://grepcode.com/file/repo1.maven.org/maven2/org.apache.lucene/lucene-core/5.2.0/org/apache/lucene/util/PriorityQueue.java#PriorityQueue

Here is a simple modification that specializes it for ints:

这是一个简单的修改，专门用于整数：

/*
 * 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;
    }
}

The way you implement betterThandecides whether it will behave as a min or max heap. This is how it's used:

您实现的方式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;
}

---

---

Some interest was expressed in the performance of this approach vs. the simple linear scan from user rakeb.void. These are the results, sizepertaining to the input size, always looking for 16 top elements:

有人对这种方法的性能与来自用户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

Conclusion: constant factors working against the heap approach are quite low. The breakeven point is around 70-80 input elements and from then on the simple approach loses steeply. Note that the constant factor stems from the final operation of extracting items in sort order. If this is not needed (i.e., just a setof the best items is enough), the we can simply retrieve the internal heaparray directly and ignore the heap[0]element which is not used by the algorithm. In that case this solution beats one like rakib.void's even for the smallest input size (I tested with 4 top elements out of 32).

结论：对堆方法起作用的常数因素非常低。盈亏平衡点大约是 70-80 个输入元素，从那时起，简单的方法急剧下降。请注意，常数因子源于按排序顺序提取项目的最终操作。如果不需要（即，只需一组最好的项目就足够了），我们可以简单地直接检索内部heap数组并忽略heap[0]算法未使用的元素。在这种情况下，即使对于最小的输入大小（我使用 32 个元素中的 4 个顶部元素进行了测试），该解决方案也能胜过rakib.void之类的解决方案。

回答by Andreas

As an alternative to sorting, here is the logic. You figure out the code.

作为排序的替代方法，这里是逻辑。你找出代码。

Keep a list (or array) of the top X values found so far. Will of course start out empty.

保留迄今为止找到的前 X 个值的列表（或数组）。当然开始时是空的。

For each new value (iteration), check against top X list.

对于每个新值（迭代），检查前 X 列表。

If top X list is shorter than X, add value.

如果顶部 X 列表比 X 短，则添加值。

If top X list is full, check if new value is greater than any value. If it is, remove smallest value from top X list and add new value.

如果顶部 X 列表已满，请检查新值是否大于任何值。如果是，从顶部 X 列表中删除最小值并添加新值。

Hint: Code will be better if top X list is sorted.

提示：如果对 top X 列表进行排序，代码会更好。

回答by Vargan

First of all, you can't use the iconstant with largearray. igoes up to 10, while largelength is 5. Use a separate variable for that and increment when you add a new value.

首先，您不能将i常量与large数组一起使用。i最多为 10，而large长度为 5。为此使用一个单独的变量，并在添加新值时递增。

Second, this logic is not retrieving the max values, you need to go over your array fully, retrieve the max value and add it to your array. Then you have to it again. You can write a first loop which use large.lengthas a condition and the inner loop which will use array.length. Or, you can use recursion.

其次，此逻辑不是检索最大值，您需要完全遍历数组，检索最大值并将其添加到数组中。然后你必须再次这样做。您可以编写large.length用作条件的第一个循环和将使用array.length. 或者，您可以使用递归。

回答by Jordi Castilla

If you don't want to sort you can check lower number and it's position and replace. WORKING DEMO HERE.

如果您不想排序，您可以检查较低的数字及其位置并替换。工作演示在这里。

public static void main(String[] args) {
    int array[] = {33,55,13,46,87,42,10,34,43,56};
    int mArray[] = new int[5];
    int j = 0;

    for(int i = 0; i < array.length; i++) {
        if (array[i] > lower(mArray)) {
            mArray[lowerPos(mArray)] = array[i];
        }
    }

    System.out.println(Arrays.toString(mArray));
}

public static int lower(int[] array) {
    int lower = Integer.MAX_VALUE;
    for (int n : array) {
        if (n < lower)
            lower = n;
    }
    return lower;
}

public static int lowerPos(int[] array) {
    int lower = Integer.MAX_VALUE;
    int lowerPos = 0;
    for (int n = 0; n < array.length; n++) {
        if (array[n] < lower) {
            lowerPos = n;
            lower = array[n];
        }
    }

    return lowerPos;
}

OUTPUT:

输出：

[43, 55, 56, 46, 87]

回答by SomeJavaGuy

Here is another approach:

这是另一种方法：

public static void main(String args[]){  

     int i;
     int largestSize = 4;
     int array[] = {33,55,13,46,87,42,10,34};
     // copy first 4 elemets, they can just be the highest 
     int large[]= Arrays.copyOf(array, largestSize);
     // get the smallest value of the large array before the first start
     int smallest = large[0];
     int smallestIndex = 0;
     for (int j = 1;j<large.length;++j) {
         if (smallest > large[j]) {
             smallest = large[j];
             smallestIndex = j;
         } 
     }
     // First Loop start one elemnt after the copy
     for(i = large.length; i < array.length; i++) 
     {
         // get the smallest value and index of the large array
         if(smallest  < array[i])
         {
             large[smallestIndex] = array[i];
             // check the next smallest value
             smallest = large[0];
             smallestIndex = 0;
             for (int j = 1;j<large.length;++j) {
                 if (smallest > large[j]) {
                     smallest = large[j];
                     smallestIndex = j;
                 } 
             }
         }
     }
     for (int j = 0; j<large.length; j++)
     {
         System.out.println("Largest 5 : "+large[j]);
     }
     System.out.println();
     System.out.println("Largest is: "+ getHighest(large));

}  

private static int getHighest(int[] array) {
    int highest = array[0];
    for (int i = 1;i<array.length;++i) {
        if (highest < array[i]) {
            highest = array[i];
        }
    }
    return highest;
}

回答by OldCurmudgeon

You could do this properly in an OOp way. This maintains a list of the n largest values of a list of offered values.

您可以以面向对象的方式正确执行此操作。这维护了一个提供值列表的 n 个最大值的列表。

class Largest<T extends Comparable<T>> {

    // Largest so far - null if we haven't yet seen that many.
    List<T> largest;

    public Largest(int n) {
        // Build my list.
        largest = new ArrayList(n);
        // Clear it.
        for (int i = 0; i < n; i++) {
            largest.add(i, null);
        }
    }

    public void offer(T next) {
        // Where to put it - or -1 if nowhere.
        int place = -1;
        // Must replace only the smallest replaceable one.
        T smallest = null;
        for (int i = 0; i < largest.size(); i++) {
            // What's there?
            T l = largest.get(i);
            if (l == null) {
                // Always replace null.
                place = i;
                break;
            }
            if (l.compareTo(next) < 0) {
                // Only replace the smallest.
                if (smallest == null || l.compareTo(smallest) < 0) {
                    // Remember here but keep looking in case there is a null or a smaller.
                    smallest = l;
                    place = i;
                }
            }
        }
        if (place != -1) {
            // Replace it.
            largest.set(place, next);
        }
    }

    public List<T> get() {
        return largest;
    }
}

public void test() {
    Integer array[] = {33, 55, 13, 46, 87, 42, 10, 34, 43, 56};
    Largest<Integer> l = new Largest<>(5);
    for (int i : array) {
        l.offer(i);
    }
    List<Integer> largest = l.get();
    Collections.sort(largest);
    System.out.println(largest);
    // Check it.
    List<Integer> asList = Arrays.asList(array);
    Collections.sort(asList);
    asList = asList.subList(asList.size() - largest.size(), asList.size());
    System.out.println(asList);
}

For larger numbers you can improve the algorithm using binarySearchto find the best place to put the new item instead of blindly walking the whole list. This has the added benefit of returning a sorted list.

对于较大的数字，您可以使用binarySearch找到放置新项目的最佳位置来改进算法，而不是盲目地遍历整个列表。这具有返回排序列表的额外好处。

class Largest<T extends Comparable<T>> {

    // Largest so far - null if we haven't yet seen that many.
    List<T> largest;
    // Limit.
    final int n;

    public Largest(int n) {
        // Build my list.
        largest = new ArrayList(n + 1);
        this.n = n;
    }

    public void offer(T next) {
        // Try to find it in the list.
        int where = Collections.binarySearch(largest, next, Collections.reverseOrder());
        // Positive means found.
        if (where < 0) {
            // -1 means at start.
            int place = -where - 1;
            // Discard anything beyond n.
            if (place < n) {
                // Insert here.
                largest.add(place, next);
                // Trim if necessary.
                if (largest.size() > n) {
                    largest.remove(n);
                }
            }
        }
    }

    public List<T> get() {
        return largest;
    }
}

回答by Rustam

try :

尝试 ：

public static int  getMax(int max,int[] arr ){

         int pos=0;
           //Looping n-1 times, O(n)
            for( int i = 0; i < arr.length; i++) // Iterate through the First Index and compare with max
            {
                // O(1)
                if( max < arr[i])
                {
                    // O(1)
                     max = arr[i];// Change max if condition is True
                     pos=i;

                }
            }
            arr[pos]=0;

        return max;
    }




 public static void main(String[] args)  {

            int large[]=new int[10];     
            int array[] = {33,55,13,46,87,42,10,34,43,56};

            int k=0;
            for(int i=0;i<array.length;i++){
                large[k++]=getMax(0,array);

            }

            System.out.println("Largest 5 is: "+     Arrays.toString(Arrays.copyOf(large,5)));
}

output:

输出：

Largest 5 is: [87, 56, 55, 46, 43]

回答by Thomas Miller

Here is a simple solution i quickly knocked up

这是一个简单的解决方案，我很快就找到了

public class Main {
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 };

    for (int j = 0; j < array.length; j++) {
        for (i = 4; i >= 0; i--) {
            if (array[j] > large[i]) {
                if (i == 4) {
                    large[i] = array[j];
                }
                else{
                    int temp = large[i];
                    large[i] = array[j];
                    large[i+1] = temp;
                }
            }
        }
    }
    for (int j = 0; j<5; j++)
    {
        System.out.println("Largest "+ j + ":"+ large[j]);
    }
}

}

}

回答by Sebastian Mach

Sorting, regular expressions, complex data structures are fine and make programming easy. However, I constantly see them misused nowadays and no one has to wonder:

排序、正则表达式、复杂的数据结构都很好，让编程变得简单。然而，我现在经常看到它们被滥用，没有人会怀疑：

Even if computers have become thousands of times fasterover the past decades, the perceived performance still continues to not only not grow, but actually slows down. Once in your terminal application, you had instant feedback, even in Windows 3.11 or Windows 98 or Gnome 1, you often had instant feedback from your machine.

即使计算机在过去几十年中速度提高了数千倍，感知性能仍然继续不仅没有增长，而且实际上变慢了。一旦进入您的终端应用程序，您就会获得即时反馈，即使在 Windows 3.11 或 Windows 98 或 Gnome 1 中，您也经常从您的机器获得即时反馈。

But it seems that it becomes increasingly popular to not only crack nuts with a sledgehammer, but even corns of wheat with steam hammers.

但似乎不仅用大锤敲碎坚果，甚至用蒸汽锤敲碎小麦玉米也变得越来越流行。

You don't need no friggin' sorting or complex datastructures for such a small problem.Don't let me invoke Z?????????A????????L??????G??????O??????????. I cannot take it, and even if I don't have a Java compiler at hands, here's my take in C++ (but will work in Java, too).

对于这样一个小问题，您不需要繁琐的排序或复杂的数据结构。不要让我调用Z?????????A?????????L??????G??????O?????????? . 我不能接受，即使我手头没有 Java 编译器，这也是我对 C++ 的看法（但也适用于 Java）。

Basically, it initializes your 5 maxima to the lowest possible integer values. Then, it goes through your list of numbers, and for each number, it looks up into your maxima to see if it has a place there.

基本上，它将您的 5 个最大值初始化为可能的最低整数值。然后，它遍历您的数字列表，对于每个数字，它会查找您的最大值以查看它是否在那里有位置。

#include <vector>
#include <limits>    // for integer minimum
#include <iostream>  // for cout
using namespace std; // not my style, I just do so to increase readability

int main () {
    // basically, an array of length 5, initialized to the minimum integer
    vector<int> maxima(5, numeric_limits<int>::lowest());

    // your numbers
    vector<int> numbers = {33, 55, 13, 46, 87, 42, 10, 34, 43, 56};

    // go through all numbers.
    for(auto n : numbers) {

        // find smallest in maxima.
        auto smallestIndex = 0;
        for (auto m=0; m!=maxima.size(); ++m) {
            if (maxima[m] < maxima[smallestIndex]) {
                smallestIndex = m;
            }
        }

        // check if smallest is smaller than current number
        if (maxima[smallestIndex] < n)
            maxima[smallestIndex] = n;
    }

    cout << "maximum values:\n";
    for(auto m : maxima) {
        cout << " - " << m << '\n';
    }
}

It is a similar solution to rakeb.voids' answer, but flips the loops inside out and does not have to modify the input array.

它是与rakeb.voids的答案类似的解决方案，但将循环内外翻转并且不必修改输入数组。

Use steam hammers when appropriate only. Learn algorithms and datastructures. And know when NOT TO USE YOUR KUNG-FU. Otherwise, you are guilty of increasing the society's waste unecessarily and contribute to overall crapness.

仅在适当的时候使用蒸汽锤。学习算法和数据结构。并且知道什么时候不要使用你的功夫。否则，你就会为不必要地增加社会的浪费而感到内疚，并导致整体的垃圾。

---

---

(Java translation by Marko, signature adapted to zero allocation)

（由 Marko 翻译，签名适应零分配）

static int[] phresnel(int[] input, int[] output) {
  Arrays.fill(output, Integer.MIN_VALUE);
  for (int in : input) {
    int indexWithMin = 0;
    for (int i = 0; i < output.length; i++) {
      if (output[i] < output[indexWithMin]) {
        indexWithMin = i;
      }
    }
    if (output[indexWithMin] < in) {
      output[indexWithMin] = in;
    }
  }
  Arrays.sort(output);
  return output;
}