第二大的数字ArrayList

Question

我目前有这段代码：

int secondLargest = list.get(0);
int largest = list.get(0);
for (int i = 0; i < list.size(); i++)
{
    if(list.get(i) > largest)
    {
        secondLargest = largest;
        largest = list.get(i);

        if(list.get(i) > secondLargest && list.get(i) != largest)
        {
            secondLargest = list.get(i);
        }
    }
}

System.out.print("Second biggest number ");
return secondLargest;       

问题在于当我使用这段代码时（列表如下：）

list2.add(1);
list2.add(2);
list2.add(10);
list2.add(9);
list2.add(8);
list2.add(7);

“查找”次高的数字停在2，因为10是最大的数字。我该如何解决这个问题？

- newbieCoder

---

我认为最简单的方法是对数组进行排序并取第二个元素（当然，这取决于顺序，我假设它是按降序排列的）。此外，如果您可以利用集合框架，可以使用SortedSet。 - x80486

Answer 1

使用Arrays.sort(array);并获取第二个元素。

- Keith

---

对于一个大的数组来说，这种方式是比较昂贵的。 - blm

排序的时间复杂度为O(n.log(n))，而循环的时间复杂度为O(n)，因此仅使用循环更好。 - Gaël J

@Keith，你不应该仅因为提问者没有指定复杂度就给出最差的解决方案。 - Dici

@Dici 谁说这是最糟糕的解决方案了？你不知道业务需求或他的需求。我的答案只需要一行来自Java分发的可信代码；其他答案需要更多的自定义代码，因此在测试中需要更多的严格性。当考虑到权衡时，你并不总是需要构建理想的老鼠夹。 - Keith

@Keith 嗯，也许在生产代码中你会决定使用这个方法处理小型数组...或者你可以在一个实用类中编写一个快速选择方法并添加一些单元测试，这样就可以获得一个多用途的方法。从复杂度的角度来看，这是最糟糕的解决方案，如果你要在简单性和复杂性之间做出权衡，你的答案至少应该提到它。无论如何！ - Dici

Answer 2

将第二个if条件放到第一个if条件之外。因为第二大的数比最大的数小，所以你永远不会在检查最大值的if块中找到它。

int secondLargest = (int) list.get(0);
int largest = list.get(0);
for (int i = 1; i < list.size(); i++) {
  if(list.get(i) > largest) {
    secondLargest = largest;
    largest = list.get(i);
  }
  if(list.get(i) > secondLargest && list.get(i) != largest) {
    secondLargest = list.get(i);
  }
}
System.out.print("Second biggest number ");
return secondLargest;

- YoungHobbit

---

请注意，如果第二大的数字与最大的数字相同，则会失败，假设该任务将测试此边缘情况（仔细阅读要求）。 - mk.

@mk. 你的意思是当列表包含两个最大值时吗？我不认为 OP 是在尝试这样做。因为否则这个逻辑就不会出现在图片中 list.get(i) != largest。 - YoungHobbit

-1：当列表按降序排序且没有两个项具有相同的值（只有一个最大值）时，此代码会失败-- list.get（0）是列表中最大的项，list.get（1）是第二大的数字，但此代码打印“第二大的数字”和list.get（0）的值，而应该打印list.get（1）的值。 - David Cary

将第二个if改为第一个的else if。 - greybeard

无法工作的代码：List<Integer> list = Arrays.asList(10,2,9,4,5,9,6,6,8); - undefined

Answer 3

您可以使用Collections.max()函数首先在ArrayList中找到最大的数字，一旦您获得了最大的元素，找到该元素的索引并将其从数组中删除。然后再次使用Collections.max()函数来查找数组中第二大的数字。代码如下：

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(1);
al.add(2);
al.add(3);
al.add(4);
System.out.println(al);

int j = Collections.max(al);

System.out.println("Max in the array is " + j);
al.remove(al.indexOf(j));
int max2 = Collections.max(al);
System.out.println(max2);

如果需要更多细节，请告诉我。

- Srivastava

---

这意味着最高价值只会发生一次。 - greybeard

Answer 4

使用两个for循环。第一个for循环应找到最大的数字并存储其索引位置。第二个for循环应找到不在先前找到的数字的相同索引位置的最大数字。（这将确保您不会错过第二大的数字与最大数字相同的情况。）

如果您认为合适，可以使用Arrays.sort(array);，并像ɐuıɥɔɐɯ建议的那样获取第二个元素。

- mk.

---

即使为了做那个，你也不需要两个循环。你可以在一个循环中实现。为什么要增加复杂性呢？ - YoungHobbit

@YoungHobbit，实际上这样可以减少复杂度。对于像OP这样的新手来说，“找到最大值，然后找到不是最大值的最大值”比在循环中进行检查要容易得多。而且如果你所说的复杂度是O(n)，那么它仍然是O(n)。 - mk.

在第二次迭代中比较索引并不能得到第二大的数字，如果最大的数字出现多次的话，应该比较数值。 - greybeard

Answer 5

import java.util.Arrays;
import java.util.List;

public class second_highest_array {

    public static void main(String[] args) {
        //List<Integer> numlist = Arrays.asList(9,8,7,6,5,4,3,2,1,0);
        //List<Integer> numlist = Arrays.asList(0,1,2,3,4,5,6,7,8);
        //List<Integer> numlist = Arrays.asList(8,7,4,1,2,3,4,1,9,0,11,9,8);
        List<Integer> numlist = Arrays.asList(9,-8,5,4,1,7,3,2,6);
        int highestnum = numlist.get(0);
        int secondhighest = numlist.get(0);
        for(int numarr : numlist) {
            if(highestnum < numarr ) {
                secondhighest = highestnum ;
                highestnum = numarr;
            }else if(secondhighest < numarr && highestnum != numarr) {
                secondhighest = numarr;
            }else if(secondhighest == highestnum) {
                secondhighest = numarr;
            }
        }
        System.out.println("highest : "+highestnum +" :: Second Highest : "+secondhighest);
    }
}

- Shant Prakash Rai

---

我们必须添加最后一个else if条件，否则如果您的数组是降序排列，它将给出错误的输出，因为在这种情况下，第二高和最高值将相等。 - Shant Prakash Rai

必须添加[special casing secondhighest == highestnum]，只需将secondhighest初始化为Integer.MIN_VALUE。 - greybeard

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

Answer 6

没有排序和线性解决方案：

    public int compute3(List<Integer> list) {
        int max = 0, secondMax = Integer.MIN_VALUE, pre = 0;
        for(int i=0; i<list.size(); i++) {
            pre = max;
            if(list.get(i)>max) {
                max = list.get(i);
            }
            if(list.get(i)<max && list.get(i)>secondMax ) {
                secondMax = list.get(i);
            } else if(pre>secondMax && pre<max){
                secondMax = pre;
            }
        }
        return secondMax;
    }

- prashant.kr.mod

Answer 7

在循环的第一个if语句中，检查第二大的而不是最大的。以下代码将帮助您开始。

    int secondLargest = list.get(0);
    int largest = list.get(0);
    for (int i = 0; i < list.size(); i++)
    {
        if(list.get(i) > secondLargest)
        {
            if(list.get(i) > largest ) {
                secondLargest = largest;
                largest = list.get(i);
            } else {
                secondLargest = list.get(i);
            }

        }
    }

- Some guy

---

请评论下哪些方面使一个帖子不有用。 - greybeard

如果项目0达到最大值，修订1将无效。 - greybeard

Answer 8

    HashSet integers = new HashSet<>(arrayList);
    ArrayList arrayList1 = new ArrayList(integers);
    return (int) arrayList1.get(arrayList1.size()-2);

- user21679710

---

HashSet没有排序顺序。如果我将数字1、99、1000、-4添加到arrayList中，我会得到-4。 - General Grievance