Virtual Indexing

Concepts

一种 Index 映射方法。

[0, 1, 2, 3, 4, 5, 6]

||

\/

[1, 3, 5, 0, 2, 4, 6]

Original Index: i

Mapped Index: (1 + 2 * i) % (n | 1)

经典题目

324 Wiggle Sort II

找中位数（findKthSmallest），然后把 smaller half 放到 even index 上，larger half 放到 odd index 上。

用 virtual indexing & rainbow sort (or three-way partitioning) 方法，定义 [0, left) : > medium，[left, i) : = medium, [i, r] : unknown, (r, n - 1] : < medium

virtual index formula: i -> (1+2*i) % (n | 1)

def wiggleSort(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    medium = self.findKthSmallest(nums, (len(nums)+1)/2 - 1, 0, len(nums) - 1)
    print medium
    # [0, l) : > medium
    # [l, i) : = medium
    # [i, r] : unknown
    # (r, n - 1] : < medium
    
    # mapped index = (1+2*i) % (n|1)
    n = len(nums)
    l = 0
    r = len(nums) - 1
    index = 0
    
    while index <= r:
        if nums[self.mapped(index, n)] > medium:
            self.swap(nums, self.mapped(index, n), self.mapped(l, n))
            index += 1
            l += 1
        elif nums[self.mapped(index, n)] < medium:
            self.swap(nums, self.mapped(index, n), self.mapped(r, n))
            r -= 1
        else:
            index += 1

def mapped(self, i, n) :
    return (1 + 2 * i) % (n | 1)
    
    
def findKthSmallest(self, nums, target, start, end):
    mid = self.partition(nums, start, end)
    if mid == target:
        return nums[mid]
    elif mid < target:
        return self.findKthSmallest(nums, target, mid + 1, end)
    else:
        return self.findKthSmallest(nums, target, start, mid - 1)

def partition(self, nums, start, end):
    pivot = nums[end]
    left = start
    right = end -1
    while left <= right:
        if nums[left] < pivot:
            left += 1
        elif nums[right] >= pivot:
            right -= 1
        else:
            self.swap(nums, left, right)
    
    self.swap(nums, left, end)
    return left