A few AC solutions in Java with one having O(N) worst time complexity with explanation


  • 5
    L

    After seeing this question, solutions off the top of my head is to sort it. Hence, these solutions are all based on sorting the array.

    Use builtin Java sort. Since Arrays.sort has a time complexity of NLogN, its complexity is NLogN.

    private int solveByBuiltInSort(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length - k];
    }
    

    Use minimum priority queue. We can only keep k elements. The complexity of the operations by a pq is depending on how many elements it have. So we may say this method is faster than the first one.

    private int solveByPQ(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.add(num);
            if (pq.size() > k) pq.poll();
        }
        return pq.poll();
    }
    

    Lastly, the inputs are all integers. There exists a linear algorithm to sort them. So we can use LSD radix sort.

    private int solveByLinearSort(int[] nums, int k) {
        final int R = (1 << 8);
        final int bitmask = R - 1;
        int[] aux = new int[nums.length];
        for (int i = 0; i < 4; i++) {
            int[] count = new int[R + 1];
            for (int num : nums) {
                int c = (num >>> (i * 8)) & bitmask;
                count[c + 1]++;
            }
            for (int r = 0; r < R; r++) count[r + 1] += count[r];
            if (i == 3) {
                int shift1 = count[R] - count[R/2];
                int shift2 = count[R/2];
                for (int r = 0; r < R/2; r++)
                    count[r] += shift1;
                for (int r = R/2; r < R; r++)
                    count[r] -= shift2;
            }
            for (int num : nums) {
                int c = (num >>> (i * 8)) & bitmask;
                aux[count[c]++] = num;
            }
            System.arraycopy(aux, 0, nums, 0, nums.length);
        }
        return nums[nums.length - k];
    }
    

    The integers are sorted byte by byte with the if statement to cope with negative integers. When the most significant byte is considered, 0x80-0xFF should be before 0x00-0x7F.


  • 0
    M

    The last one is an interesting solution that I did not think of when I created this question for OJ. I had two solutions: (1) use minheap O(nlogk) - similar to yours (2) quickselect O(n) avg time.
    Thanks for posting the LSD Radix sort solution


  • 0
    L

    You are welcome. :D May I suggest we add in a bad input test to force a randomised quickselect implementation?


  • 0
    M

    What do you mean by 'Force a quickselect implementation'?


  • 0
    M

    Please note that quick select algorithm is faster for an array of 10000 random numbers in the range -9999999 to 9999999

    Some stats:

    QuickSelect Result: 9993080 Time: 618000

    Heap Result: 9993080 Time: 2657000

    RadixSort Result: 9993080 Time: 2017000


  • 0
    L

    @mithmatt Thanks for the stats. I actually expected RadixSort to perform better. :D But, I guess the constant factor is significant without optimising the implementation.


  • 0
    L

    I meant test cases like large ordered array (0, 1, ..., 1000000) or reversed ordered array so that the pivot choosing process has to be randomised. P.S. @ does not work does it?


  • 0
    M

    I guess the average still being O(n) makes quickselect more supreme in this case. Most of the times, the input is random.

    Quicksort goes to O(n^2) if the array is ordered somehow and pivot is chosen wrongly. But works at O(nlogn) for random inputs and pivot chosen randomly (or wisely like, avg of three random numbers already in the input).

    But with radix, the O(kn) seems promising, but that k might be a bit of a problem sometimes. I did a lot of research regarding the topic.

    My thoughts on this are that it is better to be safe and guarantee an avg O(n) with quickselect as opposed to O(kn) with radix, where you are not sure of k, without seeing the inputs or knowing the range.

    But hey, I appreciate you posting the radix solution - something I did not think about until after you posted it.


Log in to reply
 

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