复杂度为 O(n) 的数组中第二高的数字

Question

给定一个数组，我们如何找到具有 O(n) 复杂度的第二大数字，我能得到的最佳复杂度是 O(nlogn) 使用排序技术。如何获得 O(n) 时间复杂度？

Answer 1

遍历所有数组中的所有 "n" 元素并保留前两个最高编号。

Assume a[], b[] and c[] are the arrays.


first_highest = a[0];
second_highest = a[1];

for (all elements in a[], b[] and c[]) {
    if (element > first_highest) {
        first_highest = element;
    } else if (element > second_highest) {
        second_highest = element;
    }
}

Answer 2

您可以使用 QuickSelect 在 O(n) 内轻松完成。

QuickSortSelection(numbers, currentLength, k) {
    if (currentLength == 1)
      return numbers[0];
    int pivot = random number from numbers array;

int newPivotIndex = partitionAroundPivot(numbers) // check quicksort algorithm for more details - less elements go left to the pivot, bigger elements go right

if ( k == newPivotIndex )
    return pivot;
else if ( k < newPivotIndex )
    return QuickSortSelection(numbers[0..newPivotIndex-1], newPivotIndex, k)
else
   return QuickSortSelection(numbers[newPivotIndex+1..end], currentLength-newPivotIndex+1, k-newPivotIndex);
}

看我的回答：Partial selection sort vs Mergesort to find "k largest in array"

Answer 3

这是一个简单的线性解：

firstMax = max(a[0], a[1])
secondMax = min(a[0], a[1])
for elem in a:
    if elem >= firstMax:
        secondMax = firstMax
        firstMax = elem
    else if elem > secondMax:
        secondMax = elem
print(secondMax)

Answer 4

我不确定你在这里问什么：你说你得到了一个数组列表。如果你的意思是你有一个数组并且你想找到第二大元素，那么你可以简单地在第一遍中找到最大的数字并在第二遍中找到第二大的数字。这需要 O(n).

Answer 5

#Here is a simple solution in o(n) complexity


array =[]

puts "enter the size of array"

sizeOfArray  = gets.chomp.to_i

sizeOfArray.times do
        array << gets.chomp.to_i
end

if array[0] > array[1]
        highest = array[0]
        second_highest = array[1]
else
        highest = array[1]
        second_highest = array[0]
end


for i in 2..array.size - 1
        if array[i] > highest
                second_highest = highest
                highest = array[i]
        end

        if (array[i]< highest) && (array[i] > second_highest)
                second_highest = array[i]
        end
end

puts highest
puts second_highest

复杂度为 O(n) 的数组中第二高的数字

second highest number in array with O(n) complexity

arrays

algorithm