如何在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)空间要求