如何查找最大值 和分钟。 在数组中使用最小的比较？
这是一个面试问题：给定一个整数数组find最大值。 和分钟。 使用最小的比较。
显然，我可以遍历数组两次，并在最坏的情况下使用~2n比较，但我想做得更好。
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次比较。
试图改善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个比较！
这个解决scheme可以扩展到任意长度的数组。 可能可以通过类似的方法来实现合并sorting（将数组分成两半，并计算每一半的min ）。
更新：这是C：中的recursion代码
#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总比较。
所以，可能是这个解决schemesrbh.kmr暗示在他的答案。
去分而治之！
1,3,2,5
对于这个发现min，max将需要6个比较
但分开他们
1,3 —>将在一个比较中给出最小1和最大3，2,5 —>在一个比较中将给出最小2和最大5
现在我们可以比较两个分钟（1,2） – >将最终分钟作为1（一个比较），同样地，两个最大（3,5）—>将给出最终的最大为5（一个比较）
所以总共有四个比较
一个有点不同的方法，它使用整数算术，而不是比较（这是没有明确禁止）
for(int i=0;i<N;i++) { xmin += x[i]-xmin & x[i]-xmin>>31; xmax += x[i]-xmax & xmax-x[i]>>31; }
蛮力是更快！
我会喜欢有人向我展示我的方式的错误，但是，…
我比较了brute-force方法和（更漂亮）recursion分割和征服的实际运行时间。 典型的结果（对每个函数的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倍。
显然，比较的数量不是问题，但可能是重新分配的数量，以及调用recursion函数的开销（这可能解释为什么1,000,000个值的运行速度慢于10个值）。
注意事项：我在VBA中做了这个，而不是C，而且我正在比较双精度数字，并将索引返回到最小值和最大值的数组中。
这里是我使用的代码（类cPerformanceCounter不包括在这里，但使用QueryPerformanceCounter高分辨率的时间）：
Option Explicit '2014.07.02 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
一个简单的recursionalgorithm的伪代码：
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)).
在阅读问题和答案后，我决定尝试几个版本（在C＃中）。
我认为最快的将是Anton Knyazyev的一个（分支免费），这不是（在我的盒子上）。
结果：
/* comp. time(ns) minmax0 3n/2 855 minmax1 2n 805 minmax2 2n 1315 minmax3 2n 685 */
为什么minmax1和minmax3更快？ 可能是因为“分支预测器”做得不错，每次迭代都有机会，find一个新的最小值（或最大值），减less，所以预测会变得更好。
总而言之，这是一个简单的testing。 我意识到我的结论可能是：
-premature。
– 不适用于不同的平台。
假设他们是指示性的。
编辑：盈亏平衡点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; } }
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); } }
到目前为止，我的分而治之的方法：
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); } }
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))); }
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; set<int> t; for(int i=0;i<n;i++) { int x; cin>>x; t.insert(x); } set<int>::iterator s,b; s=t.begin(); b=--t.end(); cout<< *s<<" "<<*b<<endl; enter code here return 0; }
//这可以在log（n）复杂度下完成！
只需循环一次数组，logging最大值和最小值。
