Radix Sort solution using Java, O(N)


  • 0
    Y

    Visualization of radix sort: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

        public int findKthLargest(int[] nums, int k) {
            int max = nums[0], min = nums[0];
            for(int n: nums) {
                max = Math.max(max, n);
                min = Math.min(min, n);
            }
            int R = 19, exp = 1;        // R is 19 instead of 10, because nums includes negatives
            while(max/exp != 0 || min/exp != 0) {
                int[] count = new int[R];
                for(int n: nums)
                    ++count[n/exp%10 + 9];
                for(int i=1; i<R; i++)
                    count[i] += count[i-1];
                    
                int[] tmp = new int[nums.length];
                for(int i=nums.length-1; i>=0; i--)
                    tmp[--count[nums[i]/exp%10 + 9]] = nums[i];
                    
                nums = tmp;
                exp *= 10;
            }
            return nums[nums.length-k];
        }
    

Log in to reply
 

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