數組中出現超過一半的數字&&2數之和
這是個人第一篇刷題處女做，寫做的目的主要有個:
第一：記錄本身所學的知識，加深印象，鞏固基礎。
第二：分享本身的知識經驗，但願可以幫助廣大的互聯網小夥伴們。java
第一次寫算法，沒有經驗，但願小夥伴們可以指出個人錯誤，讓我繼續成長。web
第一題：給定一個序列，找出其中出現了超過一半的數。算法
第一題比較簡單，可使用方法也不少，下面介紹三中方法來解決這個問題：數組
- 排序
public int getNumMoreHalf(int[] a){ //快速排序，這裏最好是將快排寫出來，非非比較懶，就沒有寫了。 Arrays.sort(a); //咱們將一個數組排序以後，那麼a.length/2這個位置必然是出現超過一半的數。 return a[a.length/2]; }
時間複雜度：O(nlg2n)svg
空間複雜度：O(lg2n),主要體如今遞歸上。spa
- HashMap計數
public int getNumMoreHalf(int[] a){ //key:a[i] value:a[i]出現的次數 Map<Integer,Integer> map=new HashMap<>(); //統計計數 for(int i=0;i<a.length;i++){ //這個方法用來計數統計真的很方便呢，若是Map中有a[i],就把原來的值+1，不然就是0+1。 map.put(a[i],map.getOrDefault(map.get(a[i]),0)+1); } int num=0; //找到結果 for(Map.Entry<Integer,Integer> m:map.entrySet()){ if(m.getValue()>a.length/2){ num=m.getKey(); } } return num; }
時間複雜度：O(n)指針
空間複雜度：O(n)code
- 摩爾投票(2個不一樣的數相互抵消，那麼最後剩下的必定是那個超過一半的數)
public int getNumMoreHalf(int[] nums ){ int count=0,target=0; for(int i=0;i<nums.length;i++){ if(count==0) target=nums[i]; count+=nums[i]==target?1:-1; } //若是可能不存在超過一半的數，那麼咱們最後還須要判斷這個數字出現的次數知否超過一半， //由於摩爾投票算法只能求出超過一半的數，並不能求出數學上說的衆數（出現次數最多的數） return target; }
摩爾投票法：xml
- 票數和： 因爲衆數出現的次數超過數組長度的一半；若記 衆數 的票數爲 +1 ，非衆數 的票數爲 −1 ，則必定有全部數字的 票數和 > 0 。
- 票數正負抵消： 設數組 nums 中的衆數爲 x ，數組長度爲 n 。若 nums 的前 a 個數字的 票數和 = 0 ，則 數組後 (n−a) 個數字的 票數和必定仍 >0 ，即後(n−a) 個數字的 衆數仍爲 x 。
- 示意圖以下
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-GLhXEFIT-1600182283688)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20200915224736849.png)]](http://static.noobyard.com/static/loading.gif)
以上說的衆數即時出現超過通常的數。blog
時間複雜度：O(n)
空間複雜度：O(1)
第二題：輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s，找出一組便可。
這一題也是比較簡單的，一樣介紹四種方法來解決這個問題：
- 暴力破解
public int[] getTargetNum(int[] a,int target){ int sum=0; for(int i=0;i<a.length;i++){ for(int j=i+1;j<a.length;j++){ if((a[i]+a[j])==target){ return new int[]{ a[i],a[j]}; } } } return new int[]{ }; }
這個就不用寫註釋了吧，相信小夥伴都能看的懂的。
時間複雜度：O(n^2)
空間複雜度：O(1)
- 二分法
public int[] getTargetNum(int[] a,int target){ for(int i=0;i<a.length;i++){ int left=i+1,right=a.length-1,num=target-a[i]; //在暴力破解的基礎上，第二層循環使用二分法 while(left<=right){ int middle=left+(right-left)/2; if(a[middle]>num){ right=middle-1; }else if(a[middle]<num){ left=middle+1; }else { return new int[]{ a[i],a[middle]}; } } } return new int[]{ }; }
在暴力破解的基礎上，利用數組有序的特性在第二層循環使用了二分法，提升了效率。
時間複雜度：O(nlog2n)
空間複雜度：O(1)
- HashMap法
public int[] getTargetNum(int[] a,int target){ Set<Integer> set=new HashSet<>(); for(int i=0;i<a.length;i++){ //在將每個元素a[i]加入到HashMap的時候，咱們使用O(1)的時間的複雜度查看target-a[i]是否也在HashMap中。 if(set.contains(target-a[i])){ return new int[]{ target-a[i],a[i]}; } set.add(a[i]); } return new int[]{ }; }
在將每個元素a[i]加入到HashMap的時候，咱們使用O(1)的時間的複雜度查看target-a[i]是否也在HashMap中。，因爲HashSet的底層實現是Hash Map，因而我在這個就將其稱呼爲HashMap。
時間複雜度：O(n)
空間複雜度：O(n)
- 雙指針
public int[] getTargetNum(int[] a,int target){ //定義2個指針，一個指向數組的左邊，一個指向數組的右邊。 int i=0,j=a.length-1; //將2個指針向右向左移動來得到最終的答案。 while(i<j){ if(a[i]+a[j]<target){ i++; }else if(a[i]+a[j]>target){ j--; }else{ return new int[]{ a[i],a[j]}; } } return new int[]{ }; }
示意圖以下：
時間複雜度：O(n)
空間複雜度：O(1)
以上2道題都是比較簡單的題，可是都很好的體現了算法技巧與思惟，實在是入門必刷的題。