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].
In [1]:
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]
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.
In [2]:
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]
Can you do it in O(n) time and/or in-place with O(1) extra space?
In [82]:
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]
In [83]:
s = Solution()
s.wiggleSort([1,1,2,2,2,1])
In [92]:
nums = [100 - i for i in range(100)]
In [93]:
s.wiggleSort(nums)
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
In [3]:
# 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
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.
In [94]:
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)
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
In [95]:
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
In [102]:
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
In [103]:
s = Solution()
In [104]:
s.sortColors([1])
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.
In [105]:
# 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
Sort a linked list in O(n log n) time using constant space complexity.
In [107]:
# 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
In [ ]: