使用分治法找出最大和最小值

我知道這是一個愚蠢的問題，但我沒有得到這一點。在此代碼從http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html 使用分治法找出最大和最小值

public int[] maxMin(int[] a,int i,int j,int max,int min) { 
    int mid,max1,min1; 
    int result[] = new int[2]; 

    //Small(P) 
    if (i==j) max = min = a[i]; 
    else if (i==j-1) { // Another case of Small(P) 
     if (a[i] < a[j]) { 
      this.max = getMax(this.max,a[j]); 
      this.min = getMin(this.min,a[i]); 
     } 
     else { 
      this.max = getMax(this.max,a[i]); 
      this.min = getMin(this.min,a[j]); } 
     } else { 
      // if P is not small, divide P into sub-problems. 
      // Find where to split the set. 

      mid = (i + j)/2; 
      // Solve the sub-problems. 
      max1 = min1 = a[mid+1]; 
      maxMin(a, i, mid, max, min);  
      maxMin(a, mid+1, j, max1, min1); 

      // Combine the solutions. 
      if (this.max < max1) this.max = max1; 
      if (this.min > min1) this.min = min1; 
     } 

     result[0] = this.max; 
     result[1] = this.min; 
     return result; 
    } 
}

採取比方說陣列是8,5,3,7，我們必須找到最大和最小，最大的初始值和最小值= ARR [0] = 8; 第一次清單將被劃分爲8,5 我們稱之爲最大最小，最大= 8分鐘= 8，因爲我== J-1，我們將得到最大= 8，最小= 5，

下一次名單將分爲[3,7]， min1 = max1 = arr [mid + 1] = 3，我們稱MaxMin的最大值爲3，最小值爲3.因爲我等於j-1，我們將得到max = 7，分= 3，

接着比較是MAX1，max和MIN1，最小值之間執行，這是我的混亂， MAX的值，在這裏分別MAX1爲8和7，但如何??? 我們沒有修改MAX1任何地方，它就會怎麼也得值7，

按我的理解，我們曾呼籲MAXMIN，最大= 3分= 3，然後更新最大= 7分鐘= 3，但我們沒有返回這些更新的值，那麼max1和min1的值如何得到更新，我卡在這裏，請解釋一下。謝謝。

來源

2016-03-02 Raj Malhotra

當您調用this.mix和this.max時，是否有外部最小值和最大值？ – Fabich

@ Lordofdark - 這裏是鏈接到代碼http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html –

我不會把這個代碼稱爲「分而治之」 - 在感覺它在理論效率方面等同於單循環，在現實生活效率（額外函數調用）方面更差，並且更加冗長。它確實細分了問題，但與顯而易見的替代方法相比，它征服的很少。二進制搜索，Karatsuba，FFT - 是更好的例子。 – tucuxi

看起來要更新2個分別this.min外在價值（在此功能）和this.max

所有你要做的是在1個或2個元素分解，然後更新this.min和this.max，所以你也可以直接掃描數組並檢查所有int值的最小值/最大值。這並不是真正的分而治之。

這裏是真正使用分而治之的解決方案：

public int[] maxMin(int[] a,int i,int j) { 
    int localmin,localmax; 
    int mid,max1,min1,max2,min2; 
    int[] result = new int[2]; 

    //Small(P) when P is one element 
    if (i==j) { 
     localmin = a[i] 
     localmax = a[i]; 
    } 
    else { 
     // if P is not small, divide P into sub-problems. 
     // where to split the set 
     mid = (i + j)/2; 
     // Solve the sub-problems. 
     int[] result1 = maxMin(a, i, mid);  
     int[] result2 = maxMin(a, mid+1, j); 
     max1 = result1[0]; 
     min1 = result1[1]; 
     max2=result2[0]; 
     min2=result2[1]; 
     // Combine the solutions. 
     if (max1 < max2) localmax = max2; 
     else localmax=max1; 
     if (min1 < min2) localmin = min1; 
     else localmin=min2; 
    } 

    result[0] = localmax; 
    result[1] = localmin; 
    return result; 
}

來源

2016-03-02 13:53:59 Fabich

對原始博客代碼的改進不錯！我知道你從原始代碼繼承了它，但我不確信需要「另一種小（P）」的代碼。在我看來，細分代碼將處理這種情況很好（增益清晰，成本是兩個更多的函數調用。） – Bampfer

你是對的，我刪除了2個元素的情況 – Fabich

@ Lordofdark-謝謝你！這段代碼很有意義，博客的代碼完全讓我困惑。 –

坦率地說，Blogger的代碼看起來像一個爛攤子。你應該對此沒有信心。

採取的是這一行早就：

if (i==j) max = min = a[i];

傳遞到函數的值，最大值和最小值，不是曾經在這種情況下使用，他們只是設置，然後永遠失去了。另請注意，如果此行運行，則數組result既不設置也不返回。（我認爲編譯器會警告有代碼路徑不會返回值）。所以這是一個錯誤，但是因爲他從不在任何地方使用返回值，所以它可能是無害的。

代碼有時就像它是通過max和min（不能做）返回值，而代碼的其他部分傳回陣列result，或者設置this.max和this.min。

如果算法會返回錯誤的結果，我不能完全決定不運行它。它可能恰好工作。但它一團糟，如果它寫的更好，你可以看到它是如何工作的一些信心。我認爲作者應該以更純粹的功能寫作，不要依賴像this.min和this.max這樣的外部變量。

還有一點，我注意到當有人在評論中提出一個問題時，他回答說，理解算法是主要目標。「這個算法的實現非常複雜，對於你我正在用這個更新一個程序。」嘖，謝謝。

總之，找到一個不同的例子來研究。正如我最初寫的那樣，黑暗之王發佈了一個迴應，而且看起來好多了。

來源

2016-03-02 14:17:17 Bampfer

使用分治法找出最大和最小值

回答

相關問題