查找最多1.5n比較的高/低數字的算法

我一直在考慮這個作業問題。給定一個大小爲n的數組，設計一個算法，可以在最多1.5n的比較中找到高值和低值。查找最多1.5n比較的高/低數字的算法

我的第一次嘗試是

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

}

我的問題是在每次循環有以下三種可能性：

低價值發現 - 1相比是
高價值發現 - 進行了2次比較
均未找到 - 進行了2次比較

因此，對於整個數組遍歷，最多可以進行2n次比較，這與1.5n比較的最大問題的要求相差甚遠。

來源

2012-01-25 Jason

在這類問題中，最好的起始值是第一個元素。 – wildplasser

@wildplasser，你的意思是用第一個元素值初始化高和低？ – Jason

是的。這避免了選擇任意{更低，更高}可能的哨兵值。 '空陣列'的情況總是特殊的（它*有*沒有最低，最高） – wildplasser

從一對數字開始，找到局部最小和最大（n/2比較）。接下來，從n/2局部最大值（n/2比較）中找到全局最大值，並從局部分鐘（n/2比較）中找到類似的全局最小值。總比較：3 * n/2！

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons

請注意，上述解決方案更改數組。替代解決方案：

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i]

來源

2012-01-25 18:27:04 ElKamina

我基本上是通過對循環初始化器的一個變化來實現它的。如果n是偶數，則循環從i = 2開始，如果奇數i = 1。這導致（3（n-2）/ 2）+1比較偶數或3（n-1）/ 2如果奇數。 – Jason

這與ElKamina的答案相同，但由於我已經開始編寫僞代碼，所以我認爲我會完成併發布它。

這個想法是比較對值（n/2比較）對以獲得高值數組和低值數組。對於每個數組，我們再次比較數值對（2 * n/2比較）以分別獲得最高值和最低值。

n/2 + 2*n/2 = 1.5n comparisons

這裏是僞代碼：

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
}

此代碼不佔n不是偶數或初始數組爲空。

來源

2012-01-25 18:39:24 Lester

這是我在面試過程中遇到的一個問題，我從面試官那裏得到了一個小小的提示：「你如何比較兩個號碼？」（它確實有幫助）。

這裏的解釋是：

可以說我有100個號碼（你可以很容易地被N取代它，但它的工作的例子更好，如果n爲偶數）。我所做的是我將它分成50個2個數字的列表。對於每一對我做一個比較，我完成了（現在做50比較），那麼我只需要找到最小值（這是49比較）和最大值的最大值（這也是49比較以及），這樣我們必須做出49 + 49 + 50 = 148的比較。我們完成了！

備註：找我們進行如下（在僞代碼）的最小值：

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min;

而且我們發現它在（N-1）的比較。代碼的最大值幾乎相同。

來源

2013-12-13 02:34:07 BullSpread

我知道這已經得到了回答，但如果有人正在尋找另一種方式來思考這一點。這個答案與Lester's類似，但可以處理n的奇數值而不會中斷，並且仍然可以進行至多1.5n的比較。祕密在於模數。 ;）

作爲確保我們將最後一個值放在正確的子數組中的副作用，givenList中的第二個元素將進行比較並放置兩次。但是，由於我們沒有改變原始數組，所以我們只對該組的高和低有興趣，這並沒有真正的區別。

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]

來源

2017-04-10 00:39:54 StudentCoder

你可能應該解釋一下*提供的其他方式。 –

謝謝Nathan！我在那裏補充說。 – StudentCoder

查找最多1.5n比較的高/低數字的算法

回答

相關問題