Java solution using partition, O(1) space


  • 0
    W
    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
    		List<Integer> result = new ArrayList<Integer>();
    		populate(nums, 0, nums.length - 1, result);
    		return result;
    	}
    	
    	void populate(int []nums, int begin, int end, List<Integer> result) {
    		int freq = nums.length / 3;
    		if(result.size() == 2)
    			return;
    		
    		int[] range = partition(nums, begin, end);
    		if(range == null)
    		    return;
    		if(range[1] - range[0] + 1 > freq)
    			result.add(nums[range[0]]);
    		if(range[0] - begin > freq)
    			populate(nums, begin, range[0] - 1, result);
    		if(end - range[1] > freq)
    			populate(nums, range[1] + 1, end, result);
    	}
    
    	int[] partition(int[] arr, int begin, int end) {
    	    if(begin > end)
    	        return null;
    		int pivot = arr[end];
    		int i = begin;
    		for (int cur = begin; cur < end; cur++) {
    			if (arr[cur] < pivot) {
    				swap(arr, i, cur);
    				i++;
    			}
    		}
    		swap(arr, i, end);
    
    		int j = i;
    		for (int cur = i + 1; cur <= end; cur++) {
    			if (arr[cur] == arr[i]) {
    				swap(arr, j + 1, cur);
    				j++;
    			}
    		}
    
    		return new int[] { i, j };
    	}
    
    	void swap(int[] arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    }
    

    Explanation:

    1. Partition the array into 3 parts (instead of normal 2 parts that is used for QuickSort, etc). Part 1 has all the numbers less than pivot, part 2 has all the number equal to pivot and part 3 has all the numbers greater than pivot
    2. If length of part2 is greater than n/3, we add that element.
    3. Now, recursively call partition of part1 and part3 only if its size is greater than n/3

    I think this solution can be generalized to get all the numbers with more than n/k occurrences for any given k.

    This solution does pass all the test cases. However, I am not sure if it is indeed a linear time solution as well. Would appreciate comments on its running time.


  • 0
    O

    if applied to n/k, I don't think it works well. There are so many choices of pivot for n/k situation.


  • 0
    M

    My solution is similar and I think it's similar to QuickSort and QuickSelect. Worst time will be O(n^2) but average time should be indeed be considered to be like QuickSelect - (O(n).


  • 0
    W

    @bu.will.9 : pivot is only for partition. It can be randomly selected to be any of the element between begin to end. Here I am choosing the end element to be pivot. Despite any pivot chosen for partition, it does not affect the main logic


  • 0
    O

    I think you're right. Suppose the worst case, 1,2,3,... m,m,m... where m appears more than n/3 times. Then each level of recursion will cost n, n-1, n-2, ..., n-m-1 times to put every element to its proper partition, while there should be n-m-1 level of recursion. So I think it should be O(n^2) for worst case. The best case is O(n) definitely.
    So maybe the time complexity will be between O(n) to O(n^2).


  • 0
    M

    Time complexity in O(x) is O(n^2) because we usually look at the worst case to nenote the O-Notation.

    But Quicksort is technically also O(n^2) - in the real word though it is in average O(n log(n)) and similarly Quiclselect is in average O(n).

    So I think (without proof) the algorithm shown in this thread is technicially O(n^2) but in average (amortized) it should be O(n).


Log in to reply
 

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