java - 如何在Java中找到数组中第二大的数字？

Question

我只是在练习一些麻省理工学院的 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;
    }

}

Answer 1

您可以简单地执行以下操作，而不是对数组进行排序:

• 保留一个largestValue 和一个secondLargestValue
• 对每个元素遍历整个数组一次:
  • 检查当前元素是否大于largestValue:
    • 如果是这样，将 largestValue 分配给 secondLargestValue，然后将当前元素分配给 largestValue(将其视为将所有内容向下移动 1)
    • 如果不是，检查当前元素是否大于secondLargestValue
      • 如果是，则将当前元素赋给secondLargestValue
      • 如果不是，什么也不做。

O(n) 运行时间

O(1) 空间要求