O(rn) time, O(n) space; find mode, not just majority element


  • 0
    D

    One could use a radix sort to approach this problem.

    Technically it's O(n) time.

    It also takes O(n) space. In return, we can find any mode of the array, not only the mode that happens to occur in more than half of the cases.

    class Solution {
        
        private static final int RADIX = 2;
    
        public int majorityElement(int[] nums) {
            radixSort(nums);
            return mode(nums);
        }
        
        private int mode(int[] nums) {
            int n = nums[0];
            int maxN = n;
            int count = 1;
            int maxCount = count;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == n) {
                    count++;
                    if (count > maxCount) {
                        maxCount = count;
                        maxN = n;
                    }
                } else {
                    count = 1;
                    n = nums[i];
                }
            }
            
            return maxN;
        }
        
        private void radixSort(int[] nums) {
            int[] helper = new int[nums.length];
            for (int i = 0; i < 32; i++) {
                sort(nums, helper, i);
                int[] t = nums;
                nums = helper;
                helper = t;
            }
        }
    
        private void sort(int[] nums, int[] helper, int i) {
            int[] arr = new int[RADIX];
            for (int num : nums) {
                int digit = getDigit(num, i);
                arr[digit]++;
            }
    
            for (int j = 1; j < RADIX; j++) {
                arr[j] += arr[j - 1];
            }
    
            for (int k = nums.length - 1; k >= 0; k--) {
                int digit = getDigit(nums[k], i);
                helper[--arr[digit]] = nums[k];
            }
        }
    
        private int getDigit(int num, int i) {
            return (num >> i) & 1;
        }
    }
    

Log in to reply
 

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