給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數 大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例：

輸入：[3,2,3]輸出：3

2.解題過程2.1 第一個思路：首先的一個想法是針對每一個元素統計出現次數，然後取次數最多的元素記下來，代碼如下：

public int majorityElement(int[] nums) { int maxNum = 0; //記錄最大次數 int target = 0; //記錄目标值 for(int i = 0; i<nums.length;i ){ int tmp = nums[i]; int num = 0; for (int j = 0; j < nums.length; j ) { if(nums[j] == tmp){ num ; } } if(num > maxNum){ //如果次數出現了新高，則更新最大次數和目标值 target = tmp; maxNum = num; } } return target; }

分析：算法的時間複雜度是O(n*n),空間複雜度是常量O(1)；

改進之處：可以把nums.length用一個變量抽取出來

2.2 第二個思路：利用HsahMap隻遍曆一次，從而降低時間複雜度，代碼如下：

public int majorityElement1(int[] nums) { int target = -1; //目标值 int length = nums.length; HashMap<Integer,Integer> hashMap = new HashMap(length/2); //hashMap的容量盡量初始化，避免多次擴容。（初始規則：初始值 = 計劃實體數 / 0.75） for(int i = 0; i < length;i ){ if(hashMap.containsKey(nums[i])){ //如果已經包含，次數加一 hashMap.put(nums[i], hashMap.get(nums[i]) 1); } else { hashMap.put(nums[i], 1); } } // 遍曆hashMap for (Integer integer : hashMap.keySet()) { if(hashMap.get(integer) > length/2){ target = integer; break; } } return target; }

分析：算法的時間複雜度是O(n),但是用到了HashMap空間複雜度是O(N)；

2.3 第三個思路：能否一次遍曆就把目标值取出，并且不使用額外的空間？

目标值的出現總次數，減去其他值的出現總次數，結果仍是大于等于1的，有一點動态規劃的思想在

public int majorityElement(int[] nums) { int num = 1; int target = nums[0]; for(int i = 1; i<nums.length;i ){ if(nums[i]==target){ num ; } else{ num--; } if(num==0){ target = nums[i]; num = 1; } } return target; }

分析：算法的時間複雜度是O(n),空間複雜度是常量O(1)；

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部