arrays - 最大を見つける方法。そして最小値。最小限の比較を使用して配列で？

Question

これはインタビューの質問です。与えられた整数の配列から最大値を見つけてください。そして最小値。最小限の比較を使用します。

明らかに、配列を 2 回ループして~2n、最悪の場合は比較を使用できますが、もっとうまくやりたいと思います。

Answer 1

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 つの比較を行うことになり、要素の3N/2合計比較になりNます。

Answer 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つの比較だけです！

このソリューションは、任意の長さの配列に拡張できます。おそらく、マージソートと同様のアプローチで実装できます（配列を半分に分割し、半分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かもしれません。

Answer 3

比較の代わりに整数演算を使用する、やや異なるアプローチ (これは明示的に禁止されていませんでした)

for(int i=0;i<N;i++) {
  xmin += x[i]-xmin & x[i]-xmin>>31;
  xmax += x[i]-xmax & xmax-x[i]>>31;
}

Answer 4

ブルートフォースはより速いです！

ここで、私のやり方の間違いを誰かに教えてもらいたいのですが…</p>

ブルートフォース法と (より美しい) 再帰的な分割統治法との実際の実行時間を比較しました。典型的な結果 (各関数への 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 個の値よりも速く実行される理由はわかりませんが、実際に実行されました!)。

警告: これは C ではなく VBA で行いました。倍精度の数値を比較し、最小値と最大値の配列にインデックスを返していました。

これが私が使用したコードです（クラス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

Answer 5

再帰アルゴリズムの単純な擬似コード:

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)).

Answer 6

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)));
}

Answer 7

これまでの最大値と最小値を追跡しながら、配列を 1 回ループするだけです。