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


  • 77
    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?


  • 20
    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


Log in to reply
 

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