Improvement of the index mapping approach in Java. O(n) time, O(1) space


  • 0
    A

    After studying the brilliant solutions in https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java
    and https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing, I come up with this. The only improvement over https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java is the skip of the additional partition. You only need to do the quick selection of the median with a 3-way partition.

    Let M be the floor(n/2) + 1 largest element in the array, so that there are floor(n/2) numbers >= M. Let L represent the numbers > M, and S represent the numbers < M. The solution is to reorganize the array as follows: {
    Put the largest floor(n/2) numbers into all the odd positions and among them all the L's are to the left of all possible M's. Put the remaining floor((n+1)/2) elements into the even positions and among them all the M's are to the left of all S's.
    }

    Here is the proof of the correctness of the above algorithm.
    We claim that if this algorithm violates the rule for the wiggle sort, then there is no way to achieve a wiggle sort. If our algorithm violates the rule, then there is some M next to each other in the final array. In this case, there are at least floor(n/2)+1 number of M's. And since there are some M's in the odd positions, there are fewer than floor(n/2) number of L's. We show the claim by contradiction. Suppose we can still wiggle sort the array in this case. We will need to use at least one L's or S's to separate all the M's. However, there can't be more than one element in between two M's, otherwise there will be more than floor(n/2) + floor(n/2)+1 >= n number of elements. So the only possibility is that there are exactly floor(n/2)+1 number of M's, all in the even positions. However, there are fewer than floor(n/2) number of L's. So there are some S's in the odd position, separating the M's. This is a contradiction.

    Clearly the solution can be implemented by a 3-way partition with pivot = M. Then reindex the array by (2*i+1) % (n | 1) mapping the first floor(n/2) to odd, and the second floor((n+1)/2) to even.

    What confuses me is that this algorithm is slower than the one using sorting in spite that the time complexity is O(n).

    public void wiggleSort(int[] a) {
            if (a == null || a.length < 2) return;
            int n = a.length;
            int l = 0, r = n-1, rank = n/2+1;
            while(true) {
                // 3-way partition
                int i = l-1, j = l, k = r;
                int pivot = a[reindex(r,n)];
                while (j < k) {
                    if (a[reindex(j,n)] > pivot) {
                        swap(a, reindex(++i,n), reindex(j++,n));
                    } else if (a[reindex(j,n)] < pivot) {
                        swap(a, reindex(j,n), reindex(--k,n));
                    } else j++;
                }
                swap(a, reindex(j++, n), reindex(r,n));
                int p = i - l + 2, q = j - l;
                if (p <= rank && rank <= q) return;
                else if (rank > q) {
                    rank -= q;
                    l = j;
                } else r = i;
            }
        }
        // reindex 
        private int reindex(int i, int n) {
            return (2*i+1) % (n | 1);
        }
        // swap
        private void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    

Log in to reply
 

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