X2_Wiggle Sort

发表于   |   分类于 ，   |     |   阅读次数

Subsequence: order, maynot continuous

QuickSort: Average O(NlgN), worst O(N2)

MergeSort: O(NlgN)

§Q

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,

Given [3,2,1,5,6,4] and k = 2, return 5. [3,3,3,3] and k = 1, return 3.

§A

k starts with 1, Assume k is valid

  • sol1sort O(NlgN)

  • sol2 Max-Heap, O(Nlgk)

  • sol3 quick select

    randomly choose/middle as privot

    (…discard…pivot…index….)

    time complexity: n/2 + n/4 + n/8 + … = n

    duplicate -> just move it, don’t influence

    worst case: all the number is same

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
   /**
O(N) guaranteed running time + O(1) space
randomize/shuffle the input -> O(N)

This is QuickSelect from QuickSort.
     */
    public int findKthLargest(int[] nums, int k) {
        int start = 0, end = nums.length - 1, index = nums.length - k;
        while (start < end) {
            int pivot = partition(nums, start, end);
            if (pivot < index) {
                start = pivot + 1;
            } else if (pivot > index) {
                end = pivot - 1;
            } else {
                return nums[pivot];
            }
        }

        // sample input: [1]
        return nums[start];
    }

    private int partition(int[] nums, int start, int end) {
        int pivot = start;
        while (start <= end) {
            while (start <= end && nums[start] <= nums[pivot]) {
                start++;
            }
            while (start <= end && nums[end] > nums[pivot]) {
                end--;
            }
            if (start > end) {
                break;
            }
            swap(nums, start, end);
        }
        swap(nums, end, pivot);
        return end;
    }
    
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

§Sort Color

  • 0…0[l]1…1[r]2…2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void sortColors(int[] nums) {
    // If nums is very big, it is likely to often hit page default by loading
    // three sections of nums (l,m,r) and cause thrashing
    int l = 0;
    int r = nums.length - 1;
    for (int m = 0; m <= r;) {
        if (nums[m] == 0) {
            swap(nums, l++, m++); //unless l == m, left = 0; left must be 1, no need to consider again
        } else if (nums[m] == 2) {
            swap(nums, r--, m);//since right may be 0/1/2, should consider again
        } else {
            m++;
        }
    }
}
  • What if 4 section
    • 0, 1, [2,3]; then partition 2 & 3
    • more pointers?

§Wiggle Sort I

Greedy

§Wiggle Sort II

Find Median: (nums.length+1) >>> 1, O(N)

Partition: sort color + Vitural Index, O(N)

1
2
3
4
5
6
7
  n = 6 => (n | 1) = 7
  n = 7 => (n | 1) = 7
  The index mapping, (1 + 2 * index) % (n | 1)
/*
vitual position: 135024, let num[135]>num[024],
then actual position 012345 will be  wiggle sort.
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void wiggleSort2(int[] nums) {
     if (nums == null || nums.length < 2) {
         return;
     }

     int median = findKthLargest(nums, (nums.length + 1) >>> 1);
     int n = nums.length;

     int left = 0, i = 0, right = n - 1;
     // The index mapping, (1 + 2*index) % (n | 1) combined with 'Color sort'
     while (i <= right) {
         int index = newIndex(i, n);
         if (nums[index] > median) {
             swap(nums, newIndex(left++, n), index);
             i++;
         } else if (nums[index] < median) {
             swap(nums, newIndex(right--, n), index);
         } else {
             i++;
         }
     }
 }

 // n = 6 => 012345->[1 3 5 0 2 4], 6 | 1 => 7
 // n = 7 => 0123456->[1 3 5 0 2 4 6], 7 | 1 => 7

 private int newIndex(int index, int n) {
     return (1 + 2 * index) % (n | 1);
 }

§expiry key hashmap in Java

How can I implement expiry key hashmap in Java?

1
2
3
4
5
6
7
8
class ValueWithExpiration {
    V val;
    long expirationTime;
}

Map<K, ValueWithExpiration>

ttl => expirationTime

  • follow up:

    When get/put expirationTime?

    Map => linear scan ? => PriorityQueue