程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 編程之美 快速尋找滿足條件的兩個數

編程之美 快速尋找滿足條件的兩個數

編輯:C++入門知識

能否快速找出一個數組中的兩個數字,讓這兩個數字之和等於一個給定的值,為了簡化起見,我們假設這個數組中肯定存在至少一組符合要求的解。

        法一:

         最直接的方法就是,窮舉法,復雜度為O(N^2);

 


         法二:

         利用sum減去a[i],再查找sum-a[i],是否在數組裡,這時候就變成查找了,可利用二分查找;排序的復雜度為O(nlgn),查找的復雜度為O(lgn),最終的復雜度為O(nlgn);

         ,也可以利用hash查找,只不過空間復雜度增加O(N);

 


         法三:先排好序,然後,i=0,j=n-1,看arr[i]+arr[j]是否等於sum,等於停止查找,小於sum,i++;大於sum,j--;復雜度為O(N)+O(NlgN);

                

 
 

for(i=0;j=n-1;i<j;) 
   if(arr[i]+arr[j]==sum) 
        return (i,j); 
   else if(arr[i]+arr[j]<sum) 
       i++; 
   else 
       j--; 
   return (i,j); 

for(i=0;j=n-1;i<j;)
   if(arr[i]+arr[j]==sum)
     return (i,j);
   else if(arr[i]+arr[j]<sum)
    i++;
   else
    j--;
   return (i,j);

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved