程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode 229: Majority Element II

leetcode 229: Majority Element II

編輯:C++入門知識

leetcode 229: Majority Element II


Majority Element II

Total Accepted: 3172 Total Submissions: 14746

Given an integer array of size n, find all elements that appear more than⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

 

[思路]

 

 

觀察可知,數組中至多可能會有2個出現次數超過 ⌊ n/3 ⌋ 的眾數

記變量n1, n2為候選眾數; c1, c2為它們對應的出現次數

遍歷數組,記當前數字為num

若num與n1或n2相同,則將其對應的出現次數加1

否則,若c1或c2為0,則將其置為1,對應的候選眾數置為num

否則,將c1與c2分別減1

最後,再統計一次候選眾數在數組中出現的次數,若滿足要求,則返回之。


[CODE]

 

public class Solution {
    public List majorityElement(int[] nums) {
        // 1, 2
        List res = new ArrayList<>();
        if(nums==null || nums.length==0) return res;
        if(nums.length==1) {
            res.add(nums[0]);
            return res;
        }
        
        int m1 = nums[0];
        int m2 = 0;
        
        int c1 = 1;
        int c2 = 0;
        
        for(int i=1; inums.length/3) res.add(m1);
        if(c2>nums.length/3) res.add(m2);
        return res;
    }
}


 

 

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