在未排序數組中查找值

我需要找出數組中任意兩個數字的和的所有組合。如果相等，則打印它們。該問題的線性解決方案具有O（N^2）複雜性。我想過排序，然後做一個二進制比較。複雜性仍然是（NlogN + N）在未排序數組中查找值

問題是我需要找到它的所有組合。

該問題的線性解決方案例如：

//Linear search, find all the combinations 
Find(int a[], int Target) 
    { 
     for(i=0; i<arr_size; i++) 
      for(j=0; j<arr_size; j++) 
       if((a[i]+a[j]) == Target) 
        cout<<a[i]<<a[j] 
    }

有什麼辦法可以進一步降低複雜性嗎？

感謝，大師

來源

2011-12-08 Guru Govindan

「的複雜性仍然是（NlogN + N）」 - 有什麼錯一個O（NlogN）的複雜性？ –

線性解決方案應該有'if（i！= j &&（a [i] + a [j]）== Target）'。我不清楚排序如何幫助，因爲那樣你就會增加排序本身的複雜性？ – nnnnnn

你可以先過濾掉所有不可能的事。這應該只需要通過數組進行兩次迭代，並有可能顯着減少設置。如果沒有，那麼你只會失去2次迭代。對於初學者，你可以找到你的最少號碼，然後過濾掉所有值>（目標 - 最少號碼）。

來源

2011-12-08 04:59:31

稍微提高了性能

private static void find(int[] a, int target) { 

    for (int i = 0; i < a.length; i++) { 
     if (a[i] == target) { 
      System.out.println("result found"); 
      break; 
     } 
     if (a[i] > target) { 
      break; 
     } 
     for (int j = 0; j < a.length; j++) { 
      if ((i != j && (a[i] + a[j]) == target)) { 
       System.out.println("result found"); 
      } 
     } 
    } 
}

來源

2011-12-08 05:14:35

你是否假設該集合中的所有元素都是非負的？ –

是的，假設數組包含正值。 –

允許否定，你將不得不使用我上面的算法。無論如何，這是一樣的想法。 –

在未排序數組中查找值

回答

相關問題