使用錦標賽括號查找最小數字

Question

我正在編寫一個程序，必須通過錦標賽括號查找最小數字。例如，有一個陣列

int[] a = new int[4] {4, 2, 1, 3} 

並通過比較彼此相鄰的數字我必須選擇最小的一個。 （min(4, 2) -> 2,min(1, 3) -> 1，然後我比較1和2，1是最小的，所以它是勝利者，但不可能比較2和1.只有[0]帶有1，[2]帶有[ 3]等。一般情況下，[2 * i]帶有[（2 * i）+1] for(int i=0; i<a.Length/2; i++) < - 像這樣的東西

第一個問題：如果有n個數字，則整棵樹由2n-第一個括號，我應該創建一個4或7個元素的數組嗎？4看起來是一個更好的選擇

第二個問題：如果我比較4和2，而2更小我應該做一個[0] = 2，然後在比較1和3時1 = 1？最後將[0]與1比較，最少數量爲[0]？可能需要臨時int。

最後一個問題：你打算以最簡單的方式做什麼？我幾乎找不到有關此算法的任何信息。我希望你能將我的思想引入工作算法。

並不多，但我張貼我的代碼：

int[] a = new int[4] { 4, 2, 1, 3 }; 
int tmp = 0; 
for (int i = 0; i < (a.Length)/2; i++) 
{ 
    if (a[tmp] > a[tmp + 1]) 
    { 
     a[i] = a[i + 1]; 
    } 
    else if(a[tmp] < a[tmp +1]) 
    { 
     a[i] = a[i + 1]; 
    } 
    tmp = tmp + 2; 
} 

你能指出我在做什麼好，什麼應該改進？

Answer 1

有利用在C＃中設置各種功能的簡單的解決方案：

int min = myArray.Min(); 
//Call your array something other than 'a' that's generally difficult to figure out later 

或者這將循環通過所有你的價值觀的一個foreach。

int minint = myArray[0]; 
foreach (int value in myArray) { 
    if (value < minint) minint = value; 
} 

1 - 你在說什麼樹？你的數組有n個值開始，所以它將有n個值max。如果你指的是你創建的所有數組中的值的數量是2n-1，那麼它仍然不意味着你需要將所有這些數組放在一個數組中，創建一個數組，使用它，然後創建另一個數組。 C＃GC將收集一個沒有指針的引用類型的對象（不會再被使用），因此如果這是您的擔憂，那麼它會是美好的記憶方式？

2 - 發佈您的代碼。有幾個小問題，但可能你會很好地改變當前的數組值或創建一個新的數組。 Temp int將不需要。

3 - 上面的貼子算法是使用C＃提供的內置函數的「最簡單」算法。如果這是一項家庭作業，請張貼一些代碼。作爲一個普遍的方向，使用遞歸函數可能是最優雅的（一些關於合併排序的一般閱讀對你前進將證明是有用的）。

Answer 2

如果比賽風格是必須的，遞歸的方法似乎是最合適的：

int Minimum (int [] values, int start, int end) 
{ 
    if (start == end) 
     return values [start]; 
    if (end - start == 1) 
     if (values [start] < values [end]) 
     return values [start]; 
     else 
     return values [end]; 
    else 
    { 
     int middle = start + (end - start)/2; 
     int min1 = Minimum (values, start, middle); 
     int min2 = Minimum (values, middle + 1, end); 
     if (min1 < min2) 
     return min1; 
     else 
     return min2; 
    } 
} 

編輯：代碼是未經測試和錯誤有可能在下滑，因爲它已經輸入的Android應用。

編輯：忘了說你怎麼稱呼這種方法。像這樣：

int min = Minimum (myArray, 0, myArray.Length -1); 

編輯：或者創建另一個重載：剛剛

int Minimum (int [] values) 
{ 
    return Minimum (values, 0, values.Length -1); 
} 

，並呼籲使用：

int min = Minimum (myArray); 

編輯：下面是考慮到非遞歸方法（裸即此方法實際上修改陣列）：

int Minimum(int[] values) 
{ 
    int step = 1; 
    do 
    { 
     for (int i = 0; i < values.Length - step; i += step)   
      if(values[i] > values[i + step]) 
       values[i] = values[i + step]; 
     step *= 2; 
    } 
    while(step < values.Length); 

    return values[0]; 
}