<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step1:  1. Wiggle sort & K-th largest number
Wiggle sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Step3:  Wiggle sort II
https
Step5:  Follow Up
Can you do it in O(n) time and/or in-place with O(1) extra space?
Step6:  K-th largest number
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.
Note
Step8:  Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1
Step10:  Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note
Step12:  Sort Colors
https
Step14:  merge two sorted lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Step16:  Sort List
Sort a linked list in O(n log n) time using constant space complexity.
<ASSISTANT_TASK:>
Python Code:
class Solution(object):
    def wiggleSort(self, nums):
        
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        
        
        for i in range(len(nums)-1):
            if (i%2 == 0 and nums[i] > nums[i+1]) or (i%2 ==1 and nums[i] < nums[i+1]):
                nums[i], nums[i+1] = nums[i+1], nums[i]         
Explanation: 1. Wiggle sort & K-th largest number
Wiggle sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
End of explanation
class Solution(object):
    def wiggleSort(self, nums):
        
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        
        
        nums.sort()
        half = len(nums[::2]) - 1
        nums[::2], nums[1::2] = nums[half::-1], nums[:half:-1]
Explanation: Wiggle sort II
https://leetcode.com/problems/wiggle-sort-ii/?tab=Description
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. 
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
End of explanation
class Solution(object):
    def wiggleSort(self, nums):
        
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        
        
        # O(n) by partition
        n = len(nums)
        med = self.findKthLargest(nums, (n+1)/2)
        idx = lambda x: (1 + 2*x) % (n|1)
        i, j , k = 0, 0 , n-1
        while j <= k:
            if nums[idx(j)] > med:
                nums[idx(j)], nums[idx(i)] = nums[idx(i)], nums[idx(j)]
                i += 1
                j += 1
            elif nums[idx(j)] < med:
                nums[idx(j)], nums[idx(k)] = nums[idx(k)], nums[idx(j)]
                k -= 1
            else:
                j += 1
        
        print nums
        
    def partition(self, nums, l, r):
        pivot = l
        while l < r:
            if nums[l] < nums[r]:
                nums[l], nums[pivot] = nums[pivot], nums[l]
                pivot += 1
            l += 1
        
        nums[pivot], nums[r] = nums[r], nums[pivot]
        
        return pivot
    
    def findKthLargest(self, nums, k):  # k can't be 0, 1<=k <= n
        n = len(nums)
        pivot = self.partition(nums, 0, n-1)
        if pivot > n-k:
            return self.findKthLargest(nums[:pivot], pivot-(n-k)) 
        elif pivot < n-k:
            return self.findKthLargest(nums[pivot+1:], k)
        else:
            return nums[pivot]
s = Solution()
s.wiggleSort([1,1,2,2,2,1])
nums = [100 - i for i in range(100)]
s.wiggleSort(nums)
Explanation: Follow Up
Can you do it in O(n) time and/or in-place with O(1) extra space?
End of explanation
# O(nlgn) time
def findKthLargest1(self, nums, k):
    return sorted(nums, reverse=True)[k-1]
    
# O(nk) time, bubble sort idea, TLE
def findKthLargest2(self, nums, k):
    for i in xrange(k):
        for j in xrange(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                # exchange elements, time consuming
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums[len(nums)-k]
    
# O(nk) time, selection sort idea
def findKthLargest3(self, nums, k):
    for i in xrange(len(nums), len(nums)-k, -1):
        tmp = 0
        for j in xrange(i):
            if nums[j] > nums[tmp]:
                tmp = j
        nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
    return nums[len(nums)-k]
    
# O(k+(n-k)lgk) time, min-heap
def findKthLargest4(self, nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    for _ in xrange(len(nums)-k):
        heapq.heappop(heap)
    return heapq.heappop(heap)
# O(k+(n-k)lgk) time, min-heap        
def findKthLargest5(self, nums, k):
    return heapq.nlargest(k, nums)[k-1]
    
# O(n) time, quick selection
def findKthLargest(self, nums, k):
    # convert the kth largest to smallest
    return self.findKthSmallest(nums, len(nums)+1-k)
    
def findKthSmallest(self, nums, k):
    if nums:
        pos = self.partition(nums, 0, len(nums)-1)
        if k > pos+1:
            return self.findKthSmallest(nums[pos+1:], k-pos-1)
        elif k < pos+1:
            return self.findKthSmallest(nums[:pos], k)
        else:
            return nums[pos]
# choose the right-most element as pivot   
def partition(self, nums, l, r):
    low = l
    while l < r:
        if nums[l] < nums[r]:
            nums[l], nums[low] = nums[low], nums[l]
            low += 1
        l += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low
Explanation: K-th largest number
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.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.
O(n): partition --> k-th
End of explanation
class Solution(object):
    def thirdMax(self, nums):
        
        :type nums: List[int]
        :rtype: int
        
        nums = set(nums)   ## this is important!!
        if len(nums) < 3:
            return max(nums)
        nums.remove(max(nums))
        nums.remove(max(nums))
        return max(nums)
Explanation: Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
End of explanation
class Solution(object):
    def topKFrequent(self, nums, k):
        
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        
        dic, ans = {}, []
        for i in range(len(nums)):
            dic[nums[i]] = dic.get(nums[i], 0) + 1
        for num in dic:
            if len(ans) == 0 or dic[num] <= dic[ans[-1]]:
                ans.append(num)
            elif dic[num] >= dic[ans[0]]:
                ans = [num] + ans
            else:
                l, r = 0, len(ans)-1
                while l < r:
                    m = (l+r)/2
                    if dic[ans[m]] >= dic[num]:
                        l = m + 1
                    else:
                        r = m - 1
                if dic[ans[l]] >= dic[num]:
                    ans = ans[:l+1] + [num] + ans[l+1:]
                else:
                    ans = ans[:l] + [num] + ans[l:]
            if len(ans) > k:
                ans.pop()
        return ans
Explanation: Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Show Company Tags
Show Tags
Show Similar Problems
End of explanation
class Solution(object):
    def sortColors(self, nums):
        
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        
        dic = {0: 0, 1: 0, 2: 0}
        for num in nums:
            dic[num] = dic.get(num, 0) + 1
        print dic
        for i in range(len(nums)):
            if i < dic[0]:
                nums[i] = 0
            elif i < dic[0] + dic[1]:
                nums[i] = 1
            else:
                nums[i] = 2
        
s = Solution()
s.sortColors([1])
Explanation: Sort Colors
https://leetcode.com/problems/sort-colors/?tab=Description
End of explanation
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        
        
        dummy = node = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        node.next = l1 or l2
        
        return dummy.next
        
        
        # if not l1:
        #     return l2
        # elif not l2:
        #     return l1
        
        # head = ListNode(0)
        # node = head
        
        # while l1 and l2:
        #     if l1.val <= l2.val:
        #         node.next = l1
        #         l1 = l1.next
        #     else:
        #         node.next = l2
        #         l2 = l2.next
        #     node = node.next
        # node.next = l1 if not l2 else l2
        # head = head.next
        
        # return head
Explanation: merge two sorted lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
End of explanation
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def sortList(self, head):
        
        :type head: ListNode
        :rtype: ListNode
        
        if not head or not head.next:
            return head
        fast, slow = head.next, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        second = slow.next
        slow.next = None
        l1 = self.sortList(head)
        l2 = self.sortList(second)
        return self.merge(l1, l2)
        
    def merge(self, l1, l2):
        dummy = node = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        node.next = l1 or l2
        
        return dummy.next
Explanation: Sort List
Sort a linked list in O(n log n) time using constant space complexity.
End of explanation
<END_TASK>