一千萬個為什麽

搜索

給定一個大小為N的數組,我需要找到在最小和最大範圍內總和的最小值數

給定一個大小為N的數組,我需要找到在最小和最大範圍內總和的最小值數。

例如:考慮一個陣列[1,2,3,4,5]。我需要從這個數組中找到最小數量的值,其總和大於5且小於8。 Ans:因為1 + 5大於5且小於8所以最小值數為2因此答案。

下面是我實現邏輯的函數。

int void CheckValue()
{
 for (i = 0; i <5; i++)
    if (a[i] > min && a[i] < max)
       return 1;
 for (i = 0; i< 4; i++)
     for (j = i + 1; j < 5; j++)
         if (a[i] + a[j] > min && a[i] + a[j] < max)
            return 2;


  for (i = 0; i < 3; i++)
      for (j = i + 1; j < 4; j++)
          for (k = j+1; k < 5; k++)
              if (a[i] + a[j] + a[k] > min && a[i] + a[j] + a[k] < max) 
                 return 3;
  for (i = 0; i < 2; i++)
      for (j = i + 1; j< 3; j++)
          for (k = j + 1; k< 4; k++)
              for (l = k + 1; l < 5; l++)
                  if (a[i] + a[j] + a[k] + a[l] > min && a[i] + a[j] + a[k] + a[l] < max)
                     return 4;
  if(a[0]+a[1]+a[2]+a[3]+a[4]>min && a[0]+a[1]+a[2]+a[3]+a[4]

它工作正常,但問題在於它的復雜性。任何人都可以提供任何進一步優化此代碼的建議,或提供更好的邏輯來實現這一點。

最佳答案

這是一個功課問題嗎?

你的問題真的不明確,但我會這樣:

把它分類。的 nlogn 即可。結果 首先添加第一個元素和最後一個元素。那是在範圍內嗎? 從一端拿出第一個指針,從開頭開始,將其移動到中間並添加中間數字和最後一個數字,第一個指針+最後一個指針。 是在範圍內?你可以將第一個指針移動到第一個和最後一個指針之間的中間位置,即:右邊是序列的3/4。

所以你在這裏使用二分搜索,在排序序列上有兩個指針。

這將為您提供估計的元素數量,這些元素將在範圍內。我希望你有這個主意。

如果總和超出範圍,您可以將第二個指針移動到中間。

這將為您提供 nlogn

請註意,這僅適用於兩個數字,我不確定您是否要求所有可能的數字添加在範圍內或只有兩個數字?

兩個數字很容易, nlogn 就可以了

所有可能的子集都是子集和問題, np hard 。指數, 2 ** n

轉載註明原文: 給定一個大小為N的數組,我需要找到在最小和最大範圍內總和的最小值數