这是一个面试题：给定一个整数数组，使用最少的比较次数找到最大值和最小值。
显然，我可以循环遍历数组两次，在最坏情况下使用 ~2n 次比较，但我希望能做得更好。
如何使用最少的比较操作在数组中找到最大值和最小值？
48
- Michael
4
6我可以想象出一种无需比较的算法（例如应用计数排序，然后选择第一个和最后一个项目）。但我想这不是重点。 - user395760
仅出于好奇，会问这种问题的是哪些公司？我被许多公司面试过，但从未见过这样的问题。 - AlienOnEarth
@AlienOnEarth 这是一家以色列初创企业。 - Michael
@user395760 一个计数排序不需要知道数组中的最小值和最大值吗？看起来你需要知道数字的范围才能初始化计数数组。 - DivideByZero
14个回答
82
1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)
使用这种方法，对于2个元素您将进行3次比较，对于N个元素总共需要3N/2次比较。
- srbhkmr
2
18第一步中我们不需要更新最小值或最大值，因此应该是
3N/2 - 2，请问这是否正确？ - Phil-ZXX它需要恰好3N/2-2次比较。 - SKR
15
尝试在srbh.kmr的答案上进行改进。假设我们有以下序列：
A = [a1, a2, a3, a4, a5]
比较 a1 和 a2，并计算 min12、max12：
if (a1 > a2)
min12 = a2
max12 = a1
else
min12 = a1
max12 = a2
同样计算min34，max34。由于a5是单独的，请保持不变...
现在比较min12和min34并计算min14，同样计算max14。最后比较min14和a5以计算min15。同样计算max15。
总共只需要进行6次比较！
这个解决方案可以扩展到任意长度的数组。可能可以通过类似归并排序（将数组分成两半，并为每半计算min max）的方法来实现。
更新：以下是C语言中的递归代码：
#include <stdio.h>
void minmax (int* a, int i, int j, int* min, int* max) {
int lmin, lmax, rmin, rmax, mid;
if (i == j) {
*min = a[i];
*max = a[j];
} else if (j == i + 1) {
if (a[i] > a[j]) {
*min = a[j];
*max = a[i];
} else {
*min = a[i];
*max = a[j];
}
} else {
mid = (i + j) / 2;
minmax(a, i, mid, &lmin, &lmax);
minmax(a, mid + 1, j, &rmin, &rmax);
*min = (lmin > rmin) ? rmin : lmin;
*max = (lmax > rmax) ? lmax : rmax;
}
}
void main () {
int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
int min, max;
minmax (a, 0, 9, &min, &max);
printf ("Min : %d, Max: %d\n", min, max);
}
我目前无法确定在 N（数组中元素的数量）方面进行比较的确切次数。但很难想象能够少于这么多次的比较。
更新：我们可以像下面这样计算比较的次数：
在这个计算树的底部，我们从原始数组中形成整数对。因此，我们有 N / 2 个叶节点。对于每个叶节点，我们执行正好 1 次比较。
通过参考完全二叉树的特性，我们有：
leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1
对于每个内部节点，我们进行2次比较。因此，我们有N - 2次比较。再加上叶子节点的N / 2次比较，总共有(3N / 2) - 2次比较。
所以，这可能是srbh.kmr在他的答案中暗示的解决方案。
- Asiri Rathnayake
9
2它可以使用分治策略来实现。 - Matthew Hall
4很好的分析。我认为你所提出的“比赛方式”的方法只是另一种观察它的方式。您也可以线性地执行，只需继续比较接下来的2个未处理对（a，b），并按我在答案中解释的方式更新最小值和最大值。我认为在两种方法中，所做的比较都将是
3N/2-2或3N/2-3/2，具体取决于奇数/偶数N。如果进行线性扫描，可以节省额外的递归空间;) - srbhkmr5请参阅Knuth第3卷，第5.3.3章，练习16。他说3N/2 - 2是最大值。 - WaywiserTundish
3引用所提到的练习题：“（I. Pohl）证明我们可以使用至多天花板函数（ceiling）(3n/2) - 2次比较，找到一组n个元素的最大值和最小值；而后者的次数不能再减少。” - WaywiserTundish
1你的分析假设了一棵完美的二叉树，但是
n 可以是奇数或者成对数可以是奇数。使用你的递归实现，这可能会导致超过 (3n/2)-2 次比较，因为你更频繁地触发需要额外比较的基本情况。 - ngmir显示剩余4条评论
5
一种略有不同的方法，使用整数算术代替比较（这并没有明确禁止）。
for(int i=0;i<N;i++) {
xmin += x[i]-xmin & x[i]-xmin>>31;
xmax += x[i]-xmax & xmax-x[i]>>31;
}
- Anton Knyazyev
1
如果a<b，则a-b<0，否则a-b>=0。因此，在前一种情况下，a-b>>31为-1（0），在后一种情况下为0。>>31基本上只是将符号位传播到整个数字。所以你得到了a +（b-a和掩码&的结果），如果掩码为0，则为a + 0 = a，如果掩码为0，则为a + b-a = b。 - Anton Knyazyev
5
采用分而治之的策略！
1,3,2,5
如果直接查找最小值和最大值，需要进行6次比较。
然而，可以将它们分开处理。
1,3 ---> will give min 1 and max 3 in one comparison
2,5 ---> will give min 2 and max 5 in one comparison
现在我们可以比较两个最小值和最大值。
min(1,2) --> will give the final min as 1 (one comparison)
max(3,5) ---> will give the final max as 5 (one comparison)
所以一共需要四次比较来找到最小值和最大值。
- saravanan
4
暴力破解更快！
我希望有人能够指出我的错误，但是...
我比较了暴力破解方法和（更优美的）递归分治方法的实际运行时间。典型结果（每个函数调用10,000,000次）：
Brute force :
0.657 seconds 10 values => 16 comparisons. Min @ 8, Max @ 10
0.604 seconds 1000000 values => 1999985 comparisons. Min @ 983277, Max @ 794659
Recursive :
1.879 seconds 10 values => 13 comparisons. Min @ 8, Max @ 10
2.041 seconds 1000000 values => 1499998 comparisons. Min @ 983277, Max @ 794659
令人惊讶的是，对于一个包含10个项的数组，暴力方法大约快了2.9倍，而对于一个包含1,000,000个项的数组，快了3.4倍。
显然，比较次数不是问题，但可能是重新分配的次数和调用递归函数的开销（我不知道为什么1,000,000个值比10个值运行得更快，但确实如此！）。
注意：我是在VBA中进行的，而不是C语言，并且我比较的是双精度数字并返回最小值和最大值在数组中的索引。
以下是我使用的代码（类cPerformanceCounter未在此处包括，但使用QueryPerformanceCounter进行高分辨率计时）：
Option Explicit
'2021-02-17
Private Const MIN_LONG As Long = -2147483648#
Private m_l_NumberOfComparisons As Long
Sub Time_MinMax()
Const LBOUND_VALUES As Long = 1
Dim l_pcOverall As cPerformanceCounter
Dim l_d_Values() As Double
Dim i As Long, _
k As Long, _
l_l_UBoundValues As Long, _
l_l_NumberOfIterations As Long, _
l_l_IndexOfMin As Long, _
l_l_IndexOfMax As Long
Set l_pcOverall = New cPerformanceCounter
For k = 1 To 2
l_l_UBoundValues = IIf(k = 1, 10, 1000000)
ReDim l_d_Values(LBOUND_VALUES To l_l_UBoundValues)
'Assign random values
Randomize '1 '1 => the same random values to be used each time
For i = LBOUND_VALUES To l_l_UBoundValues
l_d_Values(i) = Rnd
Next i
For i = LBOUND_VALUES To l_l_UBoundValues
l_d_Values(i) = Rnd
Next i
'This keeps the total run time in the one-second neighborhood
l_l_NumberOfIterations = 10000000 / l_l_UBoundValues
'——————— Time Brute Force Method —————————————————————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
IndexOfMinAndMaxDoubleBruteForce _
l_d_Values, _
LBOUND_VALUES, _
l_l_UBoundValues, _
l_l_IndexOfMin, _
l_l_IndexOfMax
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Brute-Force " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
'——————— End Time Brute Force Method —————————————————————————————————————
'——————— Time Brute Force Using Individual Calls —————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
l_l_IndexOfMin = IndexOfMinDouble(l_d_Values)
l_l_IndexOfMax = IndexOfMaxDouble(l_d_Values)
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Individual " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
'——————— End Time Brute Force Using Individual Calls —————————————————————
'——————— Time Recursive Divide and Conquer Method ————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
l_d_Values, _
LBOUND_VALUES, _
l_l_UBoundValues, _
l_l_IndexOfMin, l_l_IndexOfMax
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Recursive " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
'——————— End Time Recursive Divide and Conquer Method ————————————————————
Next k
End Sub
'Recursive divide and conquer
Sub IndexOfMinAndMaxDoubleRecursiveDivideAndConquer( _
i_dArray() As Double, _
i_l_LBound As Long, _
i_l_UBound As Long, _
o_l_IndexOfMin As Long, _
o_l_IndexOfMax As Long)
Dim l_l_IndexOfLeftMin As Long, _
l_l_IndexOfLeftMax As Long, _
l_l_IndexOfRightMin As Long, _
l_l_IndexOfRightMax As Long, _
l_l_IndexOfMidPoint As Long
If (i_l_LBound = i_l_UBound) Then 'Only one element
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = i_l_LBound
ElseIf (i_l_UBound = (i_l_LBound + 1)) Then 'Only two elements
If (i_dArray(i_l_LBound) > i_dArray(i_l_UBound)) Then
o_l_IndexOfMin = i_l_UBound
o_l_IndexOfMax = i_l_LBound
Else
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = i_l_UBound
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Else 'More than two elements => recurse
l_l_IndexOfMidPoint = (i_l_LBound + i_l_UBound) / 2
'Find the min of the elements in the left half
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
i_dArray, _
i_l_LBound, _
l_l_IndexOfMidPoint, _
l_l_IndexOfLeftMin, _
l_l_IndexOfLeftMax
'Find the min of the elements in the right half
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer i_dArray, _
l_l_IndexOfMidPoint + 1, _
i_l_UBound, _
l_l_IndexOfRightMin, _
l_l_IndexOfRightMax
'Return the index of the lower of the two values returned
If (i_dArray(l_l_IndexOfLeftMin) > i_dArray(l_l_IndexOfRightMin)) Then
o_l_IndexOfMin = l_l_IndexOfRightMin
Else
o_l_IndexOfMin = l_l_IndexOfLeftMin
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
'Return the index of the lower of the two values returned
If (i_dArray(l_l_IndexOfLeftMax) > i_dArray(l_l_IndexOfRightMax)) Then
o_l_IndexOfMax = l_l_IndexOfLeftMax
Else
o_l_IndexOfMax = l_l_IndexOfRightMax
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
End If
End Sub
Sub IndexOfMinAndMaxDoubleBruteForce( _
i_dArray() As Double, _
i_l_LBound As Long, _
i_l_UBound As Long, _
o_l_IndexOfMin As Long, _
o_l_IndexOfMax As Long)
Dim i As Long
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = o_l_IndexOfMin
For i = i_l_LBound + 1 To i_l_UBound
'Usually we will do two comparisons
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 2
If (i_dArray(i) < i_dArray(o_l_IndexOfMin)) Then
o_l_IndexOfMin = i
'We don't need to do the ElseIf comparison
m_l_NumberOfComparisons = m_l_NumberOfComparisons - 1
ElseIf (i_dArray(i) > i_dArray(o_l_IndexOfMax)) Then
o_l_IndexOfMax = i
End If
Next i
End Sub
Function IndexOfMinDouble( _
i_dArray() As Double _
) As Long
Dim i As Long
On Error GoTo EWE
IndexOfMinDouble = LBound(i_dArray)
For i = IndexOfMinDouble + 1 To UBound(i_dArray)
If (i_dArray(i) < i_dArray(IndexOfMinDouble)) Then
IndexOfMinDouble = i
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Next i
On Error GoTo 0
Exit Function
EWE:
On Error GoTo 0
IndexOfMinDouble = MIN_LONG
End Function
Function IndexOfMaxDouble( _
i_dArray() As Double _
) As Long
Dim i As Long
On Error GoTo EWE
IndexOfMaxDouble = LBound(i_dArray)
For i = IndexOfMaxDouble + 1 To UBound(i_dArray)
If (i_dArray(i) > i_dArray(IndexOfMaxDouble)) Then
IndexOfMaxDouble = i
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Next i
On Error GoTo 0
Exit Function
EWE:
On Error GoTo 0
IndexOfMaxDouble = MIN_LONG
End Function
- Rocky Scott
4
- 这不是基准测试的正确方法。
- 在小样本上，暴力算法可能效果更好。
- 如果你所声称的是真的，那么你如何解释时间复杂度计算背后的数学证明呢？这些证明表明，对数组进行暴力排序的时间复杂度为O(n^2)，而像归并排序这样的“聪明”排序则需要O(nlogn)。我们应该抛弃在计算机科学中学到的所有知识吗？ :)
@Nir：1）如何进行基准测试？2）对我来说，100万个样本似乎非常大。我的帖子在“显然”一段中提供了解释。我不会“抛弃”任何学习成果，但我会测试所有内容。处理真正的计算机时，额外的考虑因素可能会压倒一个简单的数学计算，而忽略内存分配等。在这种情况下，比较和重新分配只需要几个 CPU 指令，而递归函数的开销相对巨大。所以，这是我的猜测。我错了吗？（请友善一点。我年纪大了。） - Rocky Scott
一个有用的警告。然而，问题是“最少比较”。 - greybeard
@RockyScott 我的猜测和你一样好，但我也怀疑递归开销（为每个递归调用在堆栈上打开一个新帧）是主要因素。 - Nir Alfasi
4
阅读了问题和答案后，我决定尝试几个版本（使用C#）。
我认为最快的应该是Anton Knyazyev的版本（无分支），但在我的电脑上不是最快的。
结果：
/* comp. time(ns)
minmax0 3n/2 855
minmax1 2n 805
minmax2 2n 1315
minmax3 2n 685 */
为什么minmax1和minmax3更快？ 可能是因为“分支预测器”的工作表现良好， 每次迭代，找到新的最小值（或最大值）的机会都会减少， 因此预测变得更加准确。总之，这是一个简单的测试。 我知道我的结论可能是: -过早得出的。 -不适用于不同的平台。 让我们说它们是指示性的。 编辑：保持平衡点minmax0、minmax3: ~100项， 10,000个项目:minmax3比minmax0快3.5倍。
using System;
using sw = System.Diagnostics.Stopwatch;
class Program
{
static void Main()
{
int n = 1000;
int[] a = buildA(n);
sw sw = new sw();
sw.Start();
for (int i = 1000000; i > 0; i--) minMax3(a);
sw.Stop();
Console.Write(sw.ElapsedMilliseconds);
Console.Read();
}
static int[] minMax0(int[] a) // ~3j/2 comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (int aj; i < j; i += 2)
{
if ((ai = a[i]) < (aj = a[i + 1])) // hard to predict
{ if (ai < a0) a0 = ai; if (aj > a1) a1 = aj; }
else
{ if (aj < a0) a0 = aj; if (ai > a1) a1 = ai; }
}
if (i <= j)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] minMax1(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 3) return j < 1 ? null :
j < 2 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a0, ai = a0;
for (int i = 1; i < j; i++)
{
if ((ai = a[i]) < a0) a0 = ai;
else if (ai > a1) a1 = ai;
}
return new int[] { a0, a1 };
}
static int[] minMax2(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 2) return j == 0 ? null : new int[] { a[0], a[0] };
int a0 = a[0], a1 = a0;
for (int i = 1, ai = a[1], aj = ai; ; aj = ai = a[i])
{
ai -= a0; a0 += ai & ai >> 31;
aj -= a1; a1 += aj & -aj >> 31;
i++; if (i >= j) break;
}
return new int[] { a0, a1 };
}
static int[] minMax3(int[] a) // ~2j comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (j -= 2; i < j; i += 3)
{
ai = a[i + 0]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 1]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 2]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
}
for (j += 2; i <= j; i++)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] buildA(int n)
{
int[] a = new int[n--]; Random rand = new Random(0);
for (int j = n; n >= 0; n--) a[n] = rand.Next(-1 * j, 1 * j);
return a;
}
}
- P_P
2
递归算法的简单伪代码：
Function MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low].
return((max, min)).
else
max = A[low]; min = A[high].
return((max, min)).
end if
else
mid = low+high/2
(max_l , min_l ) = MAXMIN(A, low, mid).
(max_r , min_r ) =MAXMIN(A, mid + 1, high).
end if
Set max to the larger of max_l and max_r ;
likewise, set min to the smaller of min_l and min_r .
return((max, min)).
- Harsh Trivedi
1
迄今为止，我在Java中采用的是分治法：
public class code {
static int[] A = {444,9,8,6,199,3,0,5,3,200};
static int min = A[0], max = A[1];
static int count = 0;
public void minMax(int[] A, int i, int j) {
if(i==j) {
count = count + 2;
min = Math.min(min, A[i]);
max = Math.max(max, A[i]);
}
else if(j == i+1) {
if(A[i] > A[j]) {
count = count + 3;
min = Math.min(min, A[j]);
max = Math.max(max, A[i]);
}
else {
count = count + 3;
min = Math.min(min, A[i]);
max = Math.max(max, A[j]);
}
}
else {
minMax(A,i,(i+j)/2);
minMax(A,(i+j)/2+1,j);
}
}
public static void main(String[] args) {
code c = new code();
if(Math.min(A[0], A[1]) == A[0]) {
count++;
min = A[0];
max = A[1];
}
else {
count++;
min = A[1];
max = A[0];
}
c.minMax(A,2,A.length-1);
System.out.println("Min: "+min+" Max: "+max);
System.out.println("Total comparisons: " + count);
}
}
- anisotropic
1
import java.util.*;
class Maxmin
{
public static void main(String args[])
{
int[] arr = new int[10];
Scanner in = new Scanner(System.in);
int i, min=0, max=0;
for(i=0; i<=9; i++)
{
System.out.print("Enter any number: ");
arr[i] = in.nextInt();
}
min = arr[0];
for(i=0; i<=9; i++)
{
if(arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
System.out.println("Maximum is: " + max);
System.out.println("Minimum is: " + min);
}
}
- user3216114
1
这是微不足道的
2n比较方法，OP正在寻找具有更低渐近运行时间的解决方案。 - zstewart1
public static int[] minMax(int[] array){
int [] empty = {-1,-1};
if(array==null || array.length==0){
return empty;
}
int lo =0, hi = array.length-1;
return minMax(array,lo, hi);
}
private static int[] minMax(int []array, int lo, int hi){
if(lo==hi){
int [] result = {array[lo], array[hi]};
return result;
}else if(lo+1==hi){
int [] result = new int[2];
result[0] = Math.min(array[lo], array[hi]);
result[1] = Math.max(array[lo], array[hi]);
return result;
}else{
int mid = lo+(hi-lo)/2;
int [] left = minMax(array, lo, mid);
int [] right = minMax(array, mid+1, hi);
int []result = new int[2];
result[0] = Math.min(left[0], right[0]);
result[1] = Math.max(left[1], right[1]);
return result;
}
}
public static void main(String[] args) {
int []array = {1,2,3,4,100};
System.out.println("min and max values are "+Arrays.toString(minMax(array)));
}
- sreeprasad
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接