leetcode169. 多數元素

題目連結

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

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

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/majority-element
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
           

思路

通過資料結構棧來解決這個問題

規則：

1. 當棧為空，元素入棧
2. 當棧頂元素=目前元素，元素入棧
3. 否則出棧

代碼實作（一）

public int majorityElement(int[] nums) {
        // 初始化數組 充當棧
        int[] stack = new int[nums.length];
        int top=-1;
        for(int item:nums){
        	if(top==-1){ // 當棧為空，元素入棧
        		stack[++top]=item;
        	}else if(stack[top] == item){ // 當棧頂元素=目前元素，元素入棧
        		stack[++top]=item;
        	}else{
        		top--; //否則出棧
        	}
        }
        return stack[top];
    }
           

代碼實作（二）

在上個算法基礎上優化空間複雜度，從O(n)到O(1)。

public int majorityElement(int[] nums) {
        int res =0; // 目前棧中元素
        int count = 0; // 棧中元素個數
        for(int item:nums){
			if(count == 0){//當棧為空，元素入棧
				res = item;
				count++;
			}else if(res == item){ // 當棧頂元素=目前元素，元素入棧
				count++;
			}else{
				count--;
			}
		} 
        return res;
    }
           

結果展示

參考資料

B站燈神