Step by step explanation of index mapping in Java


  • 176
    S

    The virtual index idea in the post https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
    is very brilliant! However, it takes me a while to understand why and how it works. There is no 'nth_element' in Java, but you can use 'findKthLargest' function from "https://leetcode.com/problems/kth-largest-element-in-an-array/" to get the median element in average O(n) time and O(1) space.

    Assume your original array is {6,13,5,4,5,2}. After you get median element, the 'nums' is partially sorted such that the first half is larger or equal to the median, the second half is smaller or equal to the median, i.e

    13   6   5   5   4   2
    
             M
    

    In the post https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof, we have learned that , to get wiggle sort, you want to put the number in the following way such that

    (1) elements smaller than the 'median' are put into the last even slots

    (2) elements larger than the 'median' are put into the first odd slots

    (3) the medians are put into the remaining slots.

    Index :       0   1   2   3   4   5
    Small half:   M       S       S    
    Large half:       L       L       M
    

    M - Median, S-Small, L-Large. In this example, we want to put {13, 6, 5} in index 1,3,5 and {5,4,2} in index {0,2,4}

    The index mapping, (1 + 2*index) % (n | 1) combined with 'Color sort', will do the job.

    After selecting the median element, which is 5 in this example, we continue as the following

    Mapped_idx[Left] denotes the position where the next smaller-than median element  will be inserted.
    Mapped_idx[Right] denotes the position where the next larger-than median element  will be inserted.
    
    
    Step 1: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    5    5    4    2 
                 Left
                  i
                                          Right
     nums[Mapped_idx[i]] = nums[1] = 6 > 5, so it is ok to put 6 in the first odd index 1. We increment i and left.
    
    
    Step 2: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    5    5    4    2 
                      Left
                       i
                                          Right
     nums[3] = 5 = 5, so it is ok to put 6 in the index 3. We increment i.
    
    
    Step 3: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    5    5    4    2 
                      Left
                            i
                                         Right
     nums[5] = 2 < 5, so we want to put it to the last even index 4 (pointed by Right). So, we swap nums[Mapped_idx[i]] with nums[Mapped_idx[Right]], i.e. nums[5] with nums[4], and decrement Right. 
    
    
    
    
    Step 4: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    5    5    2    4 
                      Left
                            i
                                   Right
     nums[5] = 4 < 5, so we want to put it to the second last even index 2. So, we swap nums[5] with nums[2], and decrement Right. 
    
    
    
    
    Step 5: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    4    5    2    5 
                      Left
                            i
                                Right
     nums[5] = 5 < 5, it is ok to put it there, we increment i.
    
    
    Step 6: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        13   6    4    5    2    5 
                      Left
                                 i
                                Right
     nums[0] = 13 > 5, so, we want to put it to the next odd index which is 3 (pointed by 'Left'). So, we swap nums[0] with nums[3], and increment 'Left' and 'i'.
    
    
    Step Final: 
    Original idx: 0    1    2    3    4    5  
    Mapped idx:   1    3    5    0    2    4 
    Array:        5    6    4    13   2    5 
                          Left
                                      i
                                Right
    i > Right, we get the final wiggle array 5 6 4 13 2 5 !
    

    The code is the following:

       public void wiggleSort(int[] nums) {
            int median = findKthLargest(nums, (nums.length + 1) / 2);
            int n = nums.length;
    
            int left = 0, i = 0, right = n - 1;
    
            while (i <= right) {
    
                if (nums[newIndex(i,n)] > median) {
                    swap(nums, newIndex(left++,n), newIndex(i++,n));
                }
                else if (nums[newIndex(i,n)] < median) {
                    swap(nums, newIndex(right--,n), newIndex(i,n));
                }
                else {
                    i++;
                }
            }
    
    
        }
    
        private int newIndex(int index, int n) {
            return (1 + 2*index) % (n | 1);
        }

  • 9
    M

    very helpful post, thank you so much for spending time write this


  • 0
    C
    This post is deleted!

  • 2
    Y

    Where is the method findKthLargest defined?


  • 0

    Got a question... the findKLargest is O(Nlogk). How can you say it's O(N) on the average?


  • 4
    W

    findKLargest is O(N) using quickselect.
    There is Kth element in Array (Medium) and you can check there.


  • 0
    A

    The last "while()" is so hard to understand, it took me a while to figure out how it works... Thx a lot, dude :D


  • 8
    W

    I am curious about how to come up with (1 + 2*index) % (n | 1)


  • 49
    F

    Your solution is excellent! I use more space (O(n) extra space,O(n) time) and it's easier to understand.

    public void wiggleSort(int[] nums) {
        int median=findKthLargest(nums,(nums.length+1)/2);
        int odd=1;
        int even=nums.length%2==0?nums.length-2:nums.length-1;
        int[] tmpArr=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            if(nums[i]>median){
                tmpArr[odd]=nums[i];
                odd+=2;
                continue;
            }
            if(nums[i]<median){
                tmpArr[even]=nums[i];
                even-=2;
                continue;
            }
        }
        while(odd<nums.length){
            tmpArr[odd]=median;
            odd+=2;
        }
        while(even>=0){
            tmpArr[even]=median;
            even-=2;
        }
        for(int i=0;i<nums.length;i++){
            nums[i]=tmpArr[i];
        }
    }

  • 0
    M

    @shuoshankou thanks for taking the time to explain this. just one clarification:

    "nums[3] = 5 = 5, so it is ok to put 6 in the index 3. We increment i."
    you mean 5 correct?


  • 0
    W

    @agave

    https://discuss.leetcode.com/topic/14597/solution-explained/2

    This discussion gave a "guaranteed" O(N) solution by shuffling the original list in the worst case.


  • 2
    L

    I strongly recommend read @futurehau 's method then go through the original post. It helps me a lot to more easier and quicker to understand the original post's method:)


  • 3
    L

    Refractor the original post's method. Totally same logic, just rename the variable and make the code more readable. Also added my code in Kth Largest Element in Array. The method of finding median is referred to the popular post in the discuss. Just for reference. Thanks for sharing.

    public class Solution {
        public void wiggleSort(int[] nums) {
            if (nums == null || nums.length == 0)   return;
            int len = nums.length;
            int median = findMedian(0, len-1, len/2, nums);
            int left = 0, right = len-1, i = 0;
            // map current index firstly
            while (i <= right) {
                int mappedCurIndex = newIndex(i, len);
                if (nums[mappedCurIndex] > median) {
                    int mappedLeftIndex = newIndex(left, len);
                    swap(mappedLeftIndex, mappedCurIndex, nums);
                    left++; i++;
                } else if (nums[mappedCurIndex] < median) {
                    int mappedRightIndex = newIndex(right, len);
                    swap(mappedCurIndex, mappedRightIndex, nums);
                    right--;
                } else {
                    i++;
                }
            }
        }
        // {0,1,2,3,4,5} -> {1,3,5,0,2,4}
        // find mapped new inde
        public int newIndex(int index, int len) {
            return (1+2*index) % (len|1);
        }
        // use quicksort, average O(n) time
        public int findMedian(int start, int end, int k, int[] nums) {
            if (start > end)   return Integer.MAX_VALUE;
            int pivot = nums[end];
            int indexOfWall = start;
            for (int i = start; i < end; i++) {
                if (nums[i] <= pivot) {
                    swap(i, indexOfWall, nums);
                    indexOfWall++;
                }
            }
            swap(indexOfWall, end, nums);
            if (indexOfWall == k) {
                return nums[indexOfWall];
            }
            else if (indexOfWall < k) {
                return findMedian(indexOfWall+1, end, k, nums);
            } else {
                return findMedian(start, indexOfWall-1, k, nums);
            }
        }
        public void swap(int i, int j, int[] nums) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

  • 57

    @willcomeback
    This is to explain why mapped index formula is (1 + 2*index) % (n | 1)

    Notice that by placing the median in it's place in the array we divided the array in 3 chunks: all numbers less than median are in one side, all numbers larger than median are on the other side, median is in the dead center of the array.

    We want to place any a group of numbers (larger than median) in odd slots, and another group of numbers (smaller than median) in even slots. So all numbers on left of the median < n / 2 should be in odd slots, all numbers on right of the median > n / 2 should go into even slots (remember that median is its correct place at n / 2)

    PS: I'm ignoring the discussion of odd/even array length for simplicity.

    So let's think about the first group in the odd slots, all numbers is the left side of the array should go into these odd slots. What's the formula for it? Naturally it would be:
    (1 + 2 x index) % n

    All these indexes are less than n / 2 so multiplying by 2 and add 1 (to make them go to odd place) and then mod by n will always guarantee that they are less than n.

    Original Index => Mapped Index
    0 => (1 + 2 x 0) % 6 = 1 % 6 = 1
    1 => (1 + 2 x 1) % 6 = 3 % 6 = 3
    2 => (1 + 2 x 2) % 6 = 5 % 6 = 5

    These are what's less than median, if we continue this with indexes 3, 4, 5 we will cycle again:
    3 => (1 + 2 x 3) % 6 = 7 % 6 = 1
    4 => (1 + 2 x 4) % 6 = 9 % 6 = 3
    5 => (1 + 2 x 5) % 6 = 11 % 6 = 5

    and we don't want that, so for indexes larger than n/2 we want them to be even, (n|1) does that exactly. What n|1 does it that it gets the next odd number to n if it was even
    if n = 6 for example 110 | 1 = 111 = 7
    if n = 7 for example 111 | 1 = 111 = 7

    and this is what we want, instead of cycling the odd numbers again we want them to be even, and odd % odd number is even so updating the formula to :
    (1 + 2*index) % (n | 1)

    Then we have:
    3 => (1 + 2 x 3) % 7 = 7 % 7 = 0
    4 => (1 + 2 x 4) % 7 = 9 % 7 = 2
    5 => (1 + 2 x 5) % 7 = 11 % 7 = 4


  • 0
    R
    This post is deleted!

  • 0
    T

    Use a randomized quick select to get kth largest to try to avoid worst case. There is also a more complicated way to deal with the worst case and achieve a guaranteed O(n) time. But that will require O(n/5) space.

        public int getKth(int[] nums, int l, int r, int k, Random rand) {
            if (l == r) {
                return nums[l];
            }
            int p = l-1;
            // randomize
            int n = nums.length;
            int random = rand.nextInt(r - l + 1) + l;
            swap(nums, random, r);
            int check = nums[r];
            for (int i = l; i < r; i++) {
                if (nums[i] >= check) {
                    p++;
                    swap(nums, i, p);
                }
            }
            swap(nums, p+1, r);
            p++;
            
            if (p+1-l == k) {
                return nums[p];
            } else if (p+1-l > k) {
                return getKth(nums, l, p-1, k, rand);
            } else {
                return getKth(nums, p+1, r, k-p+l-1, rand);
            }
        }
        
        public void swap(int[] nums, int a, int b) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    

  • 1
    T

    @shuoshankou
    I think the Mapped_idx[Left] should be the position of next larger-than median element and Mapped_idx[Right] should be the next smaller-than median element. Did I understand something wrong?


  • 0
    E

    @troubleomancer1 I agree with you.


Log in to reply
 

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