java Java算法在列表中查找最小和第二小的数字

Java Algo to Find smallest and second smallest Number in List

提问by crazyTechie

I need to find smallest and second smallest number in a list.

我需要在列表中找到最小和第二小的数字。

Can I do this using singleloop? Also, we need to consider the case of two multiple occurences of a number.

我可以使用单循环来做到这一点吗？此外，我们需要考虑一个数字两次多次出现的情况。

Ex: 1. from list [20,30,90,50] output 20 ,30 2. from list [30,30,90,50] output 30 ,30

例如： 1. 从列表 [20,30,90,50] 输出 20 ,30 2. 从列表 [30,30,90,50] 输出 30 ,30

plz help

请帮忙

采纳答案by crazyTechie

I am sorry, Actually I dont have list of Integers. But I ahve list of objects.

对不起，实际上我没有整数列表。但我有对象列表。

Anyways, thanks for the help. I hope the following code works

无论如何，感谢您的帮助。我希望以下代码有效

if (minimum==0 || obj.getValue() < minimum) {
    second = minimum;
    minimum= obj.getValue();
} else if (obj.getValue() < second || second==0) {
    second = obj.getValue();
}

回答by Josh Leitzel

I want to encourage you to do your homework on your own and understand the concepts behind it, so I won't post any code for you, but here are some things to guide you:

我想鼓励你自己做功课并理解它背后的概念，所以我不会为你贴任何代码，但这里有一些东西可以指导你：

• It is possible to do this with only one loop.
• Make one pass through the list, all the time saving the currentsmallest and second-smallest number. These are the smallest and second-smallest up until thispoint in the list.
• At the end, you'll notice (if you've done it correctly) that you have the smallest and second-smallest numbers.
• In the case of a duplicate number, just be sure to include an equals check in the condition you use; i.e., you'll be checking for smaller values, so use i <= smallestand i <= secondSmallestas your two conditions (as opposed to a strict smaller than comparison).

• 只用一个循环就可以做到这一点。
• 遍历列表，一直保存当前最小和第二小的数字。这是最小和第二小的，直到这个列表中的点。
• 最后，你会注意到（如果你做对了）你有最小和第二小的数字。
• 在重复数字的情况下，请确保在您使用的条件中包含一个等于检查；即，您将检查较小的值，因此使用i <= smallest和i <= secondSmallest作为您的两个条件（而不是严格小于比较）。

回答by user1324887

This can be done in recursive way using BinarySearch. Below is a BinarySearch to find the smallest. It can be extended to find smallest and second smallest (Tournament like method).

这可以使用 BinarySearch 以递归方式完成。下面是一个 BinarySearch 来找到最小的。它可以扩展到找到最小和第二小的（类似锦标赛的方法）。

public int findSmallest(int[] A, int start, int end){
    if(end == start){
        return A[start];
    }else if(start == end-1){
        return Math.min(A[start], A[end]);
    }else{
            int mid = start + (end-start)/2;
            int min1 = findSmallest(A, start, mid);
            int min2 = findSmallest(A, mid+1, end);

            return Math.min(min1, min2);    
    }
}

Here is the method to find Second smallest. Basic idea is to return the max when search size is <=2. For rest of the search return min.

这是找到第二小的方法。基本思想是当搜索大小为 时返回最大值<=2。对于其余的搜索返回分钟。

public static int findSecondSmallest(int[] A, int start, int end){
    if(end == start){
        return A[start];
    }else if(start == end-1){
        return Math.max(A[start], A[end]);
    }else{
            int mid = start + (end-start)/2;
            int min1 = findSecondSmallest(A, start, mid);
            int min2 = findSecondSmallest(A, mid+1, end);

            return Math.min(min1, min2);    
    }
} 

回答by paxdiablo

Pseudocode only since it's homework, to be turned into your language of choice. Assuming the list has two or more numbers in it (indexes 0 and 1):

伪代码只是因为它是家庭作业，才能变成你选择的语言。假设列表中有两个或多个数字（索引 0 和 1）：

set lowest to value at index 0.
set second_lowest to value at index 1.
if lowest is greater than second_lowest:
    swap lowest and second_lowest.
vary idx from 3 to last element:
    if value at index idx is less than lowest:
        set second_lowest to lowest
        set lowest to value at index idx
    else
        if value at index idx is less than second_lowest:
            set second_lowest to value at index idx

This works by basically checking every number to see if it should be the new lowest or new second lowest number. It can be done in one loop.

这通过基本上检查每个数字来查看它是否应该是新的最低或新的次低数字来工作。它可以在一个循环中完成。

What you want to do is to run this program in your head, writing down on paper what the variables get changed to. That's a good way to understand how a computer works. Consider the list [30,20,90,10,50,12,7], following the following steps:

你想要做的是在你的头脑中运行这个程序，在纸上写下变量被改变的内容。这是了解计算机工作原理的好方法。考虑列表[30,20,90,10,50,12,7]，遵循以下步骤：

lowest   second   description
------   ------   -----------
    30       20   store first two elements.
    20       30   swap them if in wrong order (they are).
    20       30   90 is not less than either so ignore.
    10       20   10 is less than lowest (20) so move
                  lowest to second, store 10 to lowest.
    10       20   50 is not less than either so ignore.
    10       12   12 is less than second (20) so
                  store 12 to second.
     7       10   7 is less than lowest (10) so move
                  lowest to second, store 7 to lowest.

回答by chetan

#include <stdio.h>
#include <limits.h> /* For INT_MAX */

/* Function to print first smallest and second smallest elements */
void print2Smallest(int arr[], int arr_size)
{
  int i, first, second;

  /* There should be atleast two elements*/
  if(arr_size < 2)
  {
    printf(" Invalid Input ");
    return;
  }            

  first = second = INT_MAX;
  for(i = 0; i < arr_size ; i ++)
  {

    /*If current element is smaller than first then update both
      first and second */
    if(arr[i] < first)
    {
      second = first;
      first = arr[i];
    }

    /* If arr[i] is in between first and second then update second  */
    else if (arr[i] < second)
    {
      second = arr[i];
    }
  }
  printf("The smallest element is %d and second Smallest element is %d",
         first, second);
}

/* Driver program to test above function */
int main()
{
  int arr[] = {12, 13, 15, 10, 35, 1};
  print2Smallest(arr, 6);
  getchar();
  return 0;
}

回答by Jonik

Call Collections.min(), then remove the element you got from the List, and call it again?

调用Collections.min()，然后从 List 中删除你得到的元素，然后再次调用它？

    List<Integer> list = Arrays.asList(20, 30, 90, 50);
    List<Integer> copy = new ArrayList<Integer>(list);
    Integer smallest = Collections.min(copy); // 20
    copy.remove(smallest);
    Integer secondSmallest = Collections.min(copy); // 30

(Making a copy not to mess with the original.)

（制作副本不要弄乱原件。）

This is probably far from the most performant solution (From Collections.min() Javadoc: "This method iterates over the entire collection, hence it requires time proportional to the size of the collection."), but it's very simple to write and maintain. :)

这可能远不是最高效的解决方案（来自 Collections.min() Javadoc：“此方法迭代整个集合，因此它需要与集合大小成正比的时间。”），但编写和维护非常简单. :)