找到数组中第二高的数字

Question

我很难理解该方法背后的逻辑,以找到数组中第二高的数字.使用的方法是找到数组中的最高值但小于先前的最高值(已经找到).我仍然无法弄清楚的是为什么|| highest_score == second_highest有必要.例如,我输入三个数字:98,56,3.没有它,最高和第二高都是98.请解释.

int second highest = score[0];  
if (score[i] > second_highest && score[i] < highest_score || highest_score == second_highest)   
    second_highest = score[i];

Answer 1

我不相信做你所做的就能解决这个问题; 我认为这掩盖了你的逻辑中的另一个问题.要找到第二高的实际上非常简单:

 static int secondHighest(int... nums) {
    int high1 = Integer.MIN_VALUE;
    int high2 = Integer.MIN_VALUE;
    for (int num : nums) {
      if (num > high1) {
        high2 = high1;
        high1 = num;
      } else if (num > high2) {
        high2 = num;
      }
    }
    return high2;
 }

这是O(N)一次通过.如果你想接受关系,那么改为if (num >= high1),但实际上,Integer.MIN_VALUE如果数组中至少有2个元素,它将返回.Integer.MIN_VALUE如果数组只包含相同的数字,它也会返回.

Answer 2

// Initialize these to the smallest value possible
int highest = Integer.MIN_VALUE;
int secondHighest = Integer.MIN_VALUE;

// Loop over the array
for (int i = 0; i < array.Length; i++) {

    // If we've found a new highest number...
    if (array[i] > highest) {

        // ...shift the current highest number to second highest
        secondHighest = highest;

        // ...and set the new highest.
        highest = array[i];
    } else if (array[i] > secondHighest)
        // Just replace the second highest
        secondHighest = array[i];
    }
}

// After exiting the loop, secondHighest now represents the second
// largest value in the array

编辑:

哎呦.伙计们,谢谢你指出我的错误.现在修复了.

Answer 3

如果second_highest最初设置为的第一个元素已经是最高元素,那么在找到下一个元素时应将其重新分配给新元素.也就是说,它被初始化为98,应该设置为56.但是,56不高于98,所以除非你做检查,否则它不会被设置.

如果最高数字出现两次,这将导致第二个最高值,而不是您在排序数组时找到的第二个元素.