Another solution (Java)


  • 0
    P

    The approach is to check every pair of array. If two elements of pair are equal than we store the value in the array from the begining. The process should be repeated while the lenght of the array is 1 or 2. If 2 elements remain so we should count one of them to find a major.

    public int majorityElement(int[] num) {
    	int[] numCopy = new int[num.length];
    	System.arraycopy(num, 0, numCopy, 0, num.length);
    	int i = num.length;
    	int j = 0;
    
        // Find one or two major candidates.
        while(i > 2) {
        	for (int k=0; k<i; k+=2) {
        		if (k+1 < i) {
        			if (num[k] == num[k+1]) {
        				num[j] = num[k];
        				j++;
        			}
        		} else {
        			num[j] = num[k];
    				j++;
        		}
        	}
        	
        	i = j;
        	j = 0;
        }
        
        // Count if there are two candidates
        // ore return if there is only one candidate
        if (i == 2) {
        	int count = 0;
        	for (int k=0; k<numCopy.length; k++) {
        		if (numCopy[k] == num[0]) {
        			count ++;
        		}
        	}
        	if (count>numCopy.length/2) {
        		return num[0];
        	} else {
        		return num[1];
        	}
        } else {
        	return num[0];
        }
    }

  • 0
    L

    One does not need to keep a hash table of all the distinct numbers. Here is a O(n) time complexity solution but with O(1) space complexity.

    public int majorityElement(int[] num) {
    	if(num == null || num.length == 0)
    		return 0;
    
        // "iter" is the current major element, and "count" is the times that 
        //     this major element appears more than the other ones combined. 	
    	int count = 1;
    	int iter = num[0];
    
    	int N = num.length;
    	
    	for(int i=1; i<N; i++){
    		if(num[i] != iter){
    			if(count == 0){
    				// new candidate
    				iter = num[i];
    				count = 1;
    			}else{
    				// count should be bigger than 0
    				count --;
    			}
    		}else{
    			count ++;
    		}
    	}
    	
    	return iter;
    }
    

  • 0
    P

    Yes. Your solution is more elegant.


Log in to reply
 

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