C++LeetCode數據結構基礎詳解
一、隻出現一次的數字
遍歷一遍數組利用異或的特性來實現(相同為0,相異為1 )
例如[4,1,2,1,2] 4和1異或為5 5和2異或為7 7和1異或為6 6和2異或為4 這樣就能找出唯一的數字瞭
public int singleNumber(int[] nums) { int res=0; for(int i=0;i<nums.length;i++){ res=res^nums[i]; } return res; }
二、多數元素
這題可以利用排序就返回中間位置元素,就是數量超過一半的數字,但是時間復雜度為O(nlogn),
利用摩爾投票法,實現遍歷一遍數組就能找到多數元素,
具體實現:定義兩個變量計數位和標記位,將計數位初始化為1 ,將標記位為數組第一個元素 如圖[2,2,1,1,1,2,2]
public int majorityElement(int[] nums) { //摩爾投票法 也叫同歸於盡法 int count=1; int res=nums[0]; for(int i=1;i<nums.length;i++){ if(res==nums[i]){ count++; }else{ count--; if(count==0){ res=nums[i]; count=1; } } } return res; }
三、三數之和
三數之和有點類似與兩數之和,但是難度確增加瞭不少
思路是先對數組進行排序,之後定義雙指針**,左指針為i+1,右指針為最後一個數組元素,進行求和找和第一個數字相等的數**
public List<List<Integer>> threeSum(int[] nums) { //排序加雙指針 Arrays.sort(nums); List <List<Integer>> list=new ArrayList<>(); if(nums==null||nums.length<3){ return list; } for(int i=0;i<nums.length-2;i++){ if(nums[i]>0){ break; } if(i>0&&nums[i]==nums[i-1]){//去掉重復元素 continue; } int left=i+1; int right=nums.length-1; while(left<right){ int temp=-nums[i]; if(nums[left]+nums[right]==temp){ list.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; while(left<right&&nums[left]==nums[left-1]) left++; while(left<right&&nums[right]==nums[right+1]) right--; }else if(nums[left]+nums[right]>temp){ right--; }else{ left++; } } } return list; }
註意:
1 .給數組排序之後判斷元素是否大於0,大於直接返回,後面元素一定大於0
2. 去掉重復的元素,如果值相同繼續指針移動
3. Arrays.asList() 是將數組轉換成List集合的方法
總結
本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!