logo标签列表

用最少的比较次数在数组中找到第二大的元素

arraysalgorithmsearch
74

对于大小为N的数组，需要多少比较次数？

2
你被允许使用多少临时存储空间？ - Michael Myers
2
@Sachin，这将会是n*log(n)次比较。排序不能更快了。 - riwalk
2
@Stargazer712：除非数组是整数。然后，您可以使用基数排序，完全不需要比较 ;-） - Steve Jessop
1
更一般地说，查找第k大的元素：https://dev59.com/UnVC5IYBdhLWcg3wjyDu - Nate Kohl
2
@Stargazer712：不需要边界：http://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations。想一想，基数排序仍然涉及循环输入数据，并且循环必须涉及终止条件的比较。它不需要是一个*有序*比较，只需要是一个相等比较。但你是对的，问题没有提到数据类型，因此正确的答案必须假定不透明数据和比较器函数。如果面试官犯了一个“int”特例（或者在真正的推动中使用字符串），那么就是0次比较... - Steve Jessop
显示剩余9条评论
23个回答
125

最优算法需要n+log n-2次比较。把元素当作参赛者，接下来进行锦标赛排序。

首先像树一样比较这些元素。

   |
  / \
 |   |
/ \ / \
x x x x
这需要n-1次比较，每个元素最多参与log n次比较。你将找到最大的元素作为获胜者。
第二大的元素必定输给了获胜者（他不能输给另一个元素），所以他是获胜者对战的log n个元素之一。你可以使用log n-1次比较来找到它们中的哪一个。
通过对手论证证明了最优性。请参见https://math.stackexchange.com/questions/1601或http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf或http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf或https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf。
2
@Jatin：不，总共需要N+log N-2步：需要N-1次比较来找到最大值，还需要log N-1次比较来找到在那些与最大元素失配的log N个元素中的最大值。 - sdcvvc
4
Jatin：创建一个二叉树，并从底部开始填充它。叶子节点是数组的元素。每个内部节点都是其两个子节点中的最大值。您需要比较的次数是内部节点数，即n-1。然后，查看最大元素的“对手”，这些是log N个元素。 - sdcvvc
1
所以这涉及一些空间复杂度，这就回答了我的问题 :) - Sreekar
1
@POOJA GUPTA：首先，找到最大和第二大的元素（就像我的答案一样）；这给出了一个logn项。第三大的元素必须输给了第一或第二大的元素，因此您需要检查输给第一最大元素的元素（这是第二个logn项）和输给第二最大元素的元素（这是第三个logn项）。 - sdcvvc
3
老实说，我不认为给出8的原因。需要比较(n+logn-2)次才能找到最大和第二大的元素，将它们称为L_1和L_2；接下来，我们找到失去与L_1相同但不是L_2的最大元素，有log n-1个候选项，这意味着需要log n-2次比较。然后，我们找到失去与L_2相同但不是L_1的最大元素，有log n-2个候选项，所以需要log n-3次比较，取其中两个的最大值，这样就可以得到n+log n-2+log n-2+log n-3+1=n+3 log n-6。不过可能还有遗漏的地方，对数应该在向上取整符号下。 - sdcvvc
显示剩余12条评论
12

你可以通过最多2·(N-1)次比较和两个变量来找到第二大的值，这两个变量分别保存最大值和第二大值：

largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
    number := numbers[i];
    if number > largest then
        secondLargest := largest;
        largest := number;
    else
        if number > secondLargest then
            secondLargest := number;
        end;
    end;
end;
如何使用2次比较在3个元素的集合中找到最大的2个元素？ - Maciej Hehl
3
你的算法对于{1,3,2}无效。它会返回1而不是2。 - x4u
1
你的算法不起作用。请在输入“3,5,4”上尝试。 - riwalk
无法工作。如果第二大的数在最大数之前，那么你将无法找到第二大的数。 - Wilson Soethe Cursino
错误：您在else部分缺少条件。您必须比较数组中的数字，如果它大于第二大的数字并且小于当前最大的数字，则需要执行操作。我的答案：https://dev59.com/wnA65IYBdhLWcg3wyh57#47029142 - Usman
显示剩余2条评论
11

使用冒泡排序或选择排序算法以降序对数组进行排序。不要完全排序数组，只需两次遍历。第一次遍历得出最大元素，第二次遍历将给出第二个最大元素。

第一次遍历的比较次数：n-1

第二次遍历的比较次数：n-2

查找第二大元素的总比较次数：2n-3

也许您可以概括这个算法。如果您需要第三个最大元素，则进行三次遍历。

通过上述策略，您不需要任何临时变量，因为冒泡排序和选择排序是就地排序算法。

2
这是一个非常聪明的解决方案。 - Akhil Jain
我对这个解决方案的时间复杂度很好奇，因为一个循环只会执行两次。 - Vikram
我的解决方案也是 2n-3。 - Rajat Saxena
2

这里是一些代码，可能不是最优的，但至少可以找到第二大的元素：

if( val[ 0 ] > val[ 1 ] )
{
    largest = val[ 0 ]
    secondLargest = val[ 1 ];
}
else
{
    largest = val[ 1 ]
    secondLargest = val[ 0 ];
}

for( i = 2; i < N; ++i )
{
    if( val[ i ] > secondLargest )
    {
        if( val[ i ] > largest )
        {
            secondLargest = largest;
            largest = val[ i ];
        }
        else
        {
            secondLargest = val[ i ];
        }
    }
}

如果数组中最大的两个元素位于开头，则至少需要N-1次比较，最坏情况下最多需要2N-3次比较（前两个元素中的一个是数组中最小的元素）。

1

Gumbo算法的PHP版本: http://sandbox.onlinephpfunctions.com/code/51e1b05dac2e648fd13e0b60f44a2abe1e4a8689 

$numbers = [10, 9, 2, 3, 4, 5, 6, 7];

$largest = $numbers[0];
$secondLargest = null;
for ($i=1; $i < count($numbers); $i++) {
    $number = $numbers[$i];
    if ($number > $largest) {
        $secondLargest = $largest;
        $largest = $number;
    } else if ($number > $secondLargest) {
        $secondLargest = $number;
    }
}

echo "largest=$largest, secondLargest=$secondLargest";
1
假设提供的数组为 inPutArray = [1,2,5,8,7,3]，期望输出为 7（第二大的数）。
 take temp array 
      temp = [0,0], int dummmy=0;
    for (no in inPutArray) {
    if(temp[1]<no)
     temp[1] = no
     if(temp[0]<temp[1]){
    dummmy = temp[0]
    temp[0] = temp[1]
    temp[1] = temp
      }
    }

    print("Second largest no is %d",temp[1])
1

第一种情况--> 9 8 7 6 5 4 3 2 1
第二种情况--> 50 10 8 25 ........
第三种情况--> 50 50 10 8 25.........
第四种情况--> 50 50 10 8 50 25....... 

public void second element()  
{
      int a[10],i,max1,max2;  
      max1=a[0],max2=a[1];  
      for(i=1;i<a.length();i++)  
      {  
         if(a[i]>max1)  
          {
             max2=max1;  
             max1=a[i];  
          }  
         else if(a[i]>max2 &&a[i]!=max1)  
           max2=a[i];  
         else if(max1==max2)  
           max2=a[i];  
      }  
}
1

抱歉，JS代码...

已测试两个输入：

a = [55,11,66,77,72];
a = [ 0, 12, 13, 4, 5, 32, 8 ];

var first = Number.MIN_VALUE;
var second = Number.MIN_VALUE;
for (var i = -1, len = a.length; ++i < len;) {
    var dist = a[i];
    // get the largest 2
    if (dist > first) {
        second = first;
        first = dist;
    } else if (dist > second) { // && dist < first) { // this is actually not needed, I believe
        second = dist;
    }
}

console.log('largest, second largest',first,second);
largest, second largest 32 13

这应该最多有 a.length*2 次比较，并且只需遍历列表一次。
1

我知道这是一个老问题，但这是我解决它的尝试，利用了锦标赛算法。它类似于@sdcvvc使用的解决方案，但我使用二维数组存储元素。

为了使事情正常运行，有两个假设：
1）数组中的元素数量是2的幂
2）数组中没有重复项

整个过程包括两个步骤：
1.通过比较两个元素来构建一个二维数组。第一行在二维数组中将是整个输入数组。下一行包含上一行比较的结果。我们在新构建的数组上继续比较并继续构建二维数组，直到达到仅包含一个元素（最大元素）的数组。
2.我们有一个二维数组，其中最后一行仅包含一个元素：最大元素。我们继续从底部到顶部进行，在每个数组中找到被最大值“打败”的元素，并将其与当前的“第二大”值进行比较。要找到被最大值击败的元素，并避免O（n）比较，我们必须存储前一行中最大元素的索引。这样，我们可以轻松检查相邻元素。在任何级别（高于根级别），相邻元素的获取方式为：

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

rootIndex 是上一层中最大（根）元素的索引。

我知道这个问题要求使用 C++，但是这是我在 Java 中尝试解决它的方法。（我使用了列表而不是数组，以避免混乱的更改数组大小和/或不必要的数组大小计算。）

public static Integer findSecondLargest(List<Integer> list) {
        if (list == null) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        List<List<Integer>> structure = buildUpStructure(list);
        System.out.println(structure);
        return secondLargest(structure);

    }

    public static List<List<Integer>> buildUpStructure(List<Integer> list) {
        List<List<Integer>> newList = new ArrayList<List<Integer>>();
        List<Integer> tmpList = new ArrayList<Integer>(list);
        newList.add(tmpList);
        int n = list.size();
        while (n>1) {
            tmpList = new ArrayList<Integer>();
            for (int i = 0; i<n; i=i+2) {
                Integer i1 = list.get(i);
                Integer i2 = list.get(i+1);
                tmpList.add(Math.max(i1, i2));
            }
            n/= 2;
            newList.add(tmpList);   
            list = tmpList;
        }
        return newList;
    }

    public static Integer secondLargest(List<List<Integer>> structure) {
        int n = structure.size();
        int rootIndex = 0;
        Integer largest = structure.get(n-1).get(rootIndex);
        List<Integer> tmpList = structure.get(n-2);
        Integer secondLargest = Integer.MIN_VALUE;
        Integer leftAdjacent = -1;
        Integer rightAdjacent = -1;
        for (int i = n-2; i>=0; i--) {
            rootIndex*=2;
            tmpList = structure.get(i);
            leftAdjacent = tmpList.get(rootIndex);
            rightAdjacent = tmpList.get(rootIndex+1); 
            if (leftAdjacent.equals(largest)) {
                if (rightAdjacent > secondLargest) {
                    secondLargest = rightAdjacent;
                }
            }
            if (rightAdjacent.equals(largest)) {
                if (leftAdjacent > secondLargest) {
                    secondLargest = leftAdjacent;
                }
                rootIndex=rootIndex+1;
            }
        }

        return secondLargest;
    }
在这里借用了你的解决方案 - http://k2code.blogspot.in/2014/03/find-out-largest-and-second-largest.html。谢谢。 - kinshuk4
0

以下解决方案需要进行2（N-1）次比较：

arr  #array with 'n' elements
first=arr[0]
second=-999999  #large negative no
i=1
while i is less than length(arr):
    if arr[i] greater than first:
        second=first
        first=arr[i]
    else:
        if arr[i] is greater than second and arr[i] less than first:
            second=arr[i]
    i=i+1
print second
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接