General

Intersection of 2 sorted arrays

while(i < a.size && j < b.size()){
  if(a.get(i) == b.get(j) && (i == 0 || a.get(i) != a.get(i-1))){
    sortedList.add(a.get(i));
    i++;
    j++;
  }
}

Merge 2 sorted arrays

The first list has enough space for list 2

while ( m >= 0 && n >= 0 ){
  a.set(writeIndex--, a.get(m) > b.get(n) ? a.get(m--): b.get(n--));
}
while ( n >= 0){
  a.set(writeIndex--, b.get(n--));
}

K-largest element

• Sort and find k, O(nlogn)

• min heap or max heap, O(nlogk)

• like quicksort, average O(n), worst O(n^2)

  1. use partition in quicksort, find the pivot == k

  2. If find k largest, k - size + 1

• Hint: quicksort 中，pivot 左邊的數字都小於等於nums[pivot]

# 使用quicksort algo, 但每次遞回只進去一個分支, 平均是 O(N)
# quicksort:
# 1. 找一個random idx swap with rightest number
# 2. i, j index, 只要nums[j] <= nums[right], swap 並 i++
# 3. swap (i , right), i為pivot, pivot左邊的數字都<=nums[pivot]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 找第K大 == 找第 N-K+1小
        return self.findKthSmallest(nums, 0, n-1, n-k+1)
    
    
    def findKthSmallest(self, nums, left, right, k):
        pivot = self.partition(nums, left, right)
        
        # 注意 比較邊界為 pivot-left
        if pivot-left == k-1:
            return nums[pivot]
        elif pivot-left < k-1:                                # 注意 比較邊界為 pivot-left
            return self.findKthSmallest(nums, pivot+1, right, k-(pivot-left)-1)
        else:
            return self.findKthSmallest(nums, left, pivot-1, k)
        
    
    def partition(self, nums, left, right):
        r = random.randrange(left, right+1)
        
        self.swap(nums, r, right)
        i = left
        for j in range(left, right):
            if nums[j] <= nums[right]:
                self.swap(nums, i, j)
                i+=1
                
        self.swap(nums, i, right)
        return i
                
                
    def swap(self, nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp

280. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

# Greedy
def wiggleSort(self, nums: List[int]) -> None:
    for i in range(len(nums)-1):
        if i%2 == 0:
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        else:
            if nums[i] < nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]

324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

    def wiggleSort(self, nums: List[int]) -> None:
        """
        sort過後，list前半從後面開始，給隔兩個鋪，再後半
        """
        nums.sort()
        half = (len(nums)+1)//2 
        nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]