如何在Java中查找数组中第二大的数字？

Question

我只是在练习一些MIT Java作业。但是，我不确定如何找到第二大的数字。http://ocw.csail.mit.edu/f/13

  public class Marathon {
    public static void main(String[] arguments) {
        String[] names = { "Elena", "Thomas", "Hamilton", "Suzie", "Phil",
                "Matt", "Alex", "Emma", "John", "James", "Jane", "Emily",
                "Daniel", "Neda", "Aaron", "Kate" };

        int[] times = { 341, 273, 278, 329, 445, 402, 388, 275, 243, 334, 412,
                393, 299, 343, 317, 265 };

        for (int i = 0; i < names.length; i++) {
            System.out.println(names[i] + ": " + times[i]);
        }

        System.out.println();
        System.out.println("Largest Timing " + Largest(times));
        System.out.println();

    }

    public static int Largest(int[] times) {
        int maxValue = times[0];

        for (int i = 1; i < times.length; i++) {
            if (times[i] > maxValue) {
                maxValue = times[i];
            }
        }
        return maxValue;
    }

}

- AppSensei

---

将数组从大到小排序，并将第二个元素标为下标？ - alex

或者只需要有两个运行中的“最大值”，一个比另一个大。 - irrelephant

会尝试一下。谢谢。 - AppSensei

@alex，对于查找最小/最大值而言，对数组进行排序是过度的。线性解决方案相当简单。 - jonvuri

是的，排序过于复杂了。请看我的回答。 - Hot Licks

@Kiyura 是的，我没有太多考虑。 - alex

Answer 1

不必对数组进行排序，只需按照以下步骤操作：

• 保留一个largestValue和一个secondLargestValue
• 遍历整个数组一次，对于每个元素：
  • 检查当前元素是否大于largestValue：
    • 如果是，则将largestValue分配给secondLargestValue，然后将当前元素分配给largestValue（可以将其视为向下移动1）
    • 如果不是，则检查当前元素是否大于secondLargestValue
      • 如果是，则将当前元素分配给secondLargestValue
      • 如果不是，则不执行任何操作。

O(n) 运行时间

O(1) 空间要求

- sampson-chen

---

哇，你们怎么想出这样的逻辑啊...我感觉自己好蠢啊哈哈。我需要继续练习。 - AppSensei

小错误，请查看dasblinkin的帖子中的评论。 - Hot Licks

@HotLicks 我没有发现这个 bug :< - sampson-chen

Answer 2

将数组排序以查找顺序统计太浪费了。您可以通过遵循类似于已有算法的算法，并使用表示第二大数字的附加变量来找到第二大元素。

目前，下一个元素可能大于最大值，或等于/小于最大值，因此单个if就足够了：

if (times[i] > maxValue) {
    maxValue = times[i];
}

有两个变量需要考虑，下一个元素可能是：

• 大于最大值 - 最大值变为第二大的数，下一个元素成为最大值。
• 小于最大值但大于第二大的数 - 下一个元素成为第二大的数。

必须特别注意初始状态。查看前两个项目，并将较大的分配给max，将较小的分配给第二大的数；如果有第三个元素，则从该元素开始循环。

以下是代码示例：

if (times[i] > maxValue) {
    secondLargest = maxValue;
    maxValue = times[i];
} else if (times[i] > secondLargest) {
    secondLargest = times[i];
}

- Sergey Kalinichenko

---

实际上，这个算法（在“编码”时）会出错，如果你有多个相同的“最大”值。"secondLargest"变量将与"largest"相同，而不是反映真正的第二大值。要正确地执行，第二个测试需要检查是否比最大值小，而不仅仅是比次大值大。 - Hot Licks

@HotLicks，这不一定是一个错误。这个问题涉及到排名（请参见链接的原始问题），而不是找到下一个最小的唯一值。事实上，即使是一个数学上正确的“第二大”算法，如果我们处理的是列表而不是集合，可能也会返回相同的结果。 - jonvuri

@Kiyura -- 我认为，如果一个算法报告的“第二大”的值与“最大”的值相同，那么它是有问题的。“第二大”意味着该值小于“最大”。 - Hot Licks

在所有数字均不同的情况下，没有必要处理并列问题。如果需要处理并列逻辑，则需要增加一个额外的 if 语句。 - Sergey Kalinichenko

在这个问题的背景下，除了int largest = 445; int secondLargest = 412;之外，没有必要编写太多的代码。 - Hot Licks

@HotLicks 是的，我猜是这样的：）：）：） - Sergey Kalinichenko

Answer 3

private static int secLargest(int[] numbers) {
        int maxVal = 0;
        int nextMaxVal = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > maxVal) {
                nextMaxVal = maxVal;
                maxVal = numbers[i];

            }
            if (numbers[i] < maxVal) {
                nextMaxVal = maxVal;
                maxVal = numbers[i];

            }
        }
        return nextMaxVal;

    }

- Saurabh

Answer 4

通常情况下：

有两个值--“largest”和“notQuite”。

将它们都初始化为-9999或其他值。

扫描列表。如果数字大于“largest”，则将“largest”设置为该数字。但在执行此操作之前，请将旧的“largest”值复制到“notQuite”中。

另一方面，如果数字比“largest”小但大于“notQuite”，则将“notQuite”设置为该数字。

当您完成所有数字的检查时，“notQuite”包含第二大的数字。

请注意，当您填写上述数字时，还可以保持“largestIndex”和“notQuiteIndex”，并使用对应的数组索引值进行填充，以便您可以标识“获胜”的值。不幸的是，如果有多个相同的“largest”或“secondLargest”值，则简单的索引方案无法工作，您需要保留某种列表。

- Hot Licks

---

最好设置一个哨兵来检查未设置的运行值，或者至少将它们设置为Integer.MIN_VALUE。 - jonvuri

@Kiyura -- 是的。对于许多情况，仅将其初始化为-1就足够了。这取决于您的数据性质。奇怪的情况是列表完全由MIN_VALUE条目组成，在这种情况下需要哨兵，因为没有“第二大”的值。 - Hot Licks

为什么这种情况需要特殊处理？如果列表完全由MIN_VALUE组成，并且您将其初始化为max和secondMax，那么它们在最后都将是正确的。 - jonvuri

取决于你对“第二大”的定义。它们可以相同吗？ - Hot Licks

在这个问题中，它们对应于排名（具体来说是参加比赛的次数），所以是的。实际上，如果多个索引具有最大值，则它们应该是。即，"取决于您的数据的性质" ;) - jonvuri

是的，但你可以有5个相同的数字，但仍然不是“第二大”。 - Hot Licks

Answer 5

    private void secondLargest(int arr[]){

    int maxOne=arr[0];
    int maxTwo=arr[1];

    for(int i=0;i<arr.length;i++){

        if(arr[i]>maxOne){

            maxTwo=maxOne;
            maxOne=arr[i];
        }else if (arr[i]>maxTwo) {

            maxTwo=arr[i];
        }

    }

    System.out.println(maxOne);
    System.out.println(maxTwo);
}

- Deepak Sharma

Answer 6

int largest=time[0];
int secondLargest=largest;
for(int i=0;i<time.length;i++){
    if(time[i]>largest){
        secondLargest=largest;
        largest=time[i];
    }
    else if(secondLargest<time[i] && time[i]<largest || secondLargest>=largest)
        secondLargest=time[i];
}
return secondLargest;

- Mircea Stefan

Answer 7

public static void main (String args[]) {
    int [] arr = {1,4,3,10,4,8,20,5,33};
    int largest = 0;
    int secondLargest = 0;
    for (int x : arr) {
        if (x > largest) {
            secondLargest = largest;
            largest = x;
        }
        else if (x > secondLargest) {
            secondLargest = x;
        }
    }
    System.out.println("secondLargest:"+secondLargest);
}

- Dheeraj

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

Answer 8

如果最大的数字出现两次，它还会提取第二大的数字，并在单个循环中完成。

import java.util.*;
public class SecondLargestInArray
{
    public static void main(String[] args)
    {
        int arr[] = {99,14,46,47,86,92,52,48,36,66,85,92};
        int largest = arr[0];
        int secondLargest = arr[0];
        System.out.println("The given array is:" );
        for (int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i]+"\t");
        }

        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i] > largest)
            {
                secondLargest = largest;
                largest = arr[i];
            }
            else if((arr[i]<largest && arr[i]>secondLargest) || largest==secondLargest)
            {
                secondLargest=arr[i];
            }
        }
        System.out.println("\nLargest number is:" + largest);
        System.out.println("\nSecond largest number is:" + secondLargest);
    }
}

- Lokesh Verma

Answer 9

更新：更改为Java。

class Main {
  public static void main(String[] args) {
    int a = Integer.MIN_VALUE;
    int b = Integer.MIN_VALUE;
    int[] arr = {44,6,43,8,9,-10,4,15,3,-30,23};

    for(int i=0; i < arr.length; i++){ 
        if( arr[i] > a || arr[i] > b ){
          if( a < b ) {
            a = arr[i];
          } else {
            b = arr[i];
          }
        }
    }  
    int secondLargest = a < b ? a : b;
    System.out.println(secondLargest);
  }
}

- Mr X

---

这个回答对OP没有任何帮助，他在问关于JAVA而不是PHP的问题。 - Wilfredo P

正如您所提到的，您的答案是用PHP编写的。请花些时间将其转换为OP所请求的Java代码。 - Conscript

@Conscript 现在已经更新，请也点赞支持一下。 - Mr X

Answer 10

在给定的数组中找到第二大的元素：

public static void findSecondMax(){
        int[] arr = {3, 2, 20, 4, 1, 9, 6, 3, 8};

        int max = 0;
        int secondMax = 0;

        for(int i =0; i< arr.length; i++) {

            if(max < arr[i]) max = arr[i];

            if((max > arr[i]) && (secondMax < arr[i])) secondMax = arr[i];

        }

        System.out.println(secondMax);
    }

- dinesh pazani