JAVA-------------------Easy Version To Understand!!!!!!!!!!!!


  • 81
    H
    	public List<Integer> majorityElement(int[] nums) {
    	if (nums == null || nums.length == 0)
    		return new ArrayList<Integer>();
    	List<Integer> result = new ArrayList<Integer>();
    	int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
    	for (int i = 0; i < len; i++) {
    		if (nums[i] == number1)
    			count1++;
    		else if (nums[i] == number2)
    			count2++;
    		else if (count1 == 0) {
    			number1 = nums[i];
    			count1 = 1;
    		} else if (count2 == 0) {
    			number2 = nums[i];
    			count2 = 1;
    		} else {
    			count1--;
    			count2--;
    		}
    	}
    	count1 = 0;
    	count2 = 0;
    	for (int i = 0; i < len; i++) {
    		if (nums[i] == number1)
    			count1++;
    		else if (nums[i] == number2)
    			count2++;
    	}
    	if (count1 > len / 3)
    		result.add(number1);
    	if (count2 > len / 3)
    		result.add(number2);
    	return result;
    }

  • 2
    Z

    why if I change some logic sentences ,it doesn't work
    for example

    if(counta == 0){    
                a=n;
                counta=1;
            }
            else
                if(a == n){
                         counta++;
                    }
            
               else
                   if(countb == 0){
                    b = n;
                    countb=1;
                    }
                    else
                      if(b == n){
                       
                        countb++;
                      }
                      else
                      {
                          counta --;
                          countb --;
                      }

  • 0
    G
    This post is deleted!

  • 0
    R

    What if the frquency becomes 5/n or 6/n or...? Then do we need to define 5 or 6 counts?
    Is there a more applicative way?


  • 27
    D

    @Reborn_ you can just use an array if it is a n/k question. it will be something like this...

    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
            int n = nums.length, k = 3;  //in this question, k=3 specifically
            List<Integer> result = new ArrayList<Integer>();
            if (n==0 || k<2) return result;
            int[] candidates = new int[k-1];
            int[] counts = new int[k-1];
            for (int num: nums) {
                boolean settled = false;
                for (int i=0; i<k-1; i++) {
                    if (candidates[i]==num) {
                        counts[i]++;
                        settled = true;
                        break;
                    } 
                }
                if (settled) continue;
                for (int i=0; i<k-1; i++) {
                    if (counts[i]==0) {
                        counts[i] = 1;
                        candidates[i] = num;
                        settled = true;
                        break;
                    } 
                }
                if (settled) continue;
                for (int i=0; i<k-1; i++) counts[i] = (counts[i] > 0) ? (counts[i]-1) : 0;
            }
            Arrays.fill(counts, 0);
            for (int num: nums) {
                for (int i=0;i<k-1; i++) {
                    if (candidates[i]==num) {
                        counts[i]++;
                        break;
                    }
                }
            }
            for (int i=0; i<k-1; i++) if (counts[i]>n/k) result.add(candidates[i]);
            return result;
        }
    }
    

  • 0
    R

    @DamaoServices thanks for your smart solution!


  • 0
    O

    How come it's easy to understand?


  • 0
    X

    @Oldman09 If you understand clearly about Major Element 1, this is definitely the easiest version to understand.


  • 1
    C

    @Oldman09 since it requires more than n /3, so there should be no more than 2 elements. hope it helps


  • 1
    Z

    nice solutions!


  • 0
    X

    @zhouyi_naive same question


  • 0
    I

    @DamaoServices This generalized solution is really nice for such n/k problems. Thanks!


  • 0
    M

    I think you missed one constraint on the last if statement, what if num1 == num2? I think it should be if(count2>len/3 && num1!=num2).


  • 0
    B

    @DamaoServices

    Hi, I think we can ignore checking counts[i] > 0 at this line:

    for (int i=0; i<k-1; i++) counts[i] = (counts[i] > 0) ? (counts[i]-1) : 0;
    

    Correct if i am wrong, thanks.


  • 0
    T

    @DamaoServices great solution, emulate your method:

    class Solution {
        public List<Integer> majorityElement(int[] nums) {
            List<Integer> res = new ArrayList<>();
            int k = 3;
            if(k<=1 || nums.length<1){
                return res;
            }
            
            
            int[] count = new int[k-1];
            int[] candidates = new int[k-1];
            Arrays.fill(count,0);
            Arrays.fill(candidates,nums[0]);
            
            for(int ele:nums){
                boolean check = false;
                for(int i=0;i<k-1;i++){
                    if(candidates[i] == ele){
                        count[i]++;
                        check = true;
                        break;
                    }
                }
                if(check == true){
                    continue;
                }
                
                for(int i=0;i<k-1;i++){
                    if(count[i]==0){
                         check = true;
                         candidates[i] = ele;
                         count[i] = 1;
                    }
                }
                if(check == true){
                    continue;
                }
                for(int i=0;i<k-1;i++){
                    count[i]--;
                }
            }
            Set<Integer> set = new HashSet<>();
            Arrays.fill(count,0);
            for(int ele : nums){
                for(int i=0;i<k-1;i++){
                    if(candidates[i]==ele){
                        count[i]++;
                    }
                    if(count[i]>nums.length/k){
                        set.add(candidates[i]);
                    }
                }
            }
            return new ArrayList<Integer>(set);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.