Description
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].
Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].
Note: You may assume all input has valid answer.
Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?
Solutions
1. Sort
# Time: O(nlogn)
# Space: O(n)
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort()
mid = len(nums[::2])
nums[::2], nums[1::2] = nums[:mid][::-1], nums[mid:][::-1]
# 44/44 cases passed (172 ms)
# Your runtime beats 86.52 % of python3 submissions
# Your memory usage beats 11.11 % of python3 submissions (15.7 MB)
2. Quick Sort - median
from random import randint
# Time: O(n)
# Space: O(1)
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def findKthLargest(nums, k):
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = randint(left, right)
new_pivot_idx = partitionAroundPivot(left, right, pivot_idx, nums)
if new_pivot_idx == k - 1:
return nums[new_pivot_idx]
elif new_pivot_idx > k - 1:
right = new_pivot_idx - 1
else: # new_pivot_idx < k - 1.
left = new_pivot_idx + 1
def partitionAroundPivot(left, right, pivot_idx, nums):
pivot_value = nums[pivot_idx]
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in range(left, right):
if nums[i] > pivot_value:
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1
nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx
def reversedTriPartitionWithVI(nums, val):
def idx(i, N):
return (1 + 2 * (i)) % N
N = len(nums) // 2 * 2 + 1
i, j, n = 0, 0, len(nums) - 1
while j <= n:
if nums[idx(j, N)] > val:
nums[idx(i, N)], nums[idx(j, N)] = nums[idx(j, N)], nums[idx(i, N)]
i += 1
j += 1
elif nums[idx(j, N)] < val:
nums[idx(j, N)], nums[idx(n, N)] = nums[idx(n, N)], nums[idx(j, N)]
n -= 1
else:
j += 1
mid = (len(nums) - 1) // 2
findKthLargest(nums, mid + 1)
reversedTriPartitionWithVI(nums, nums[mid])
# 44/44 cases passed (3140 ms)
# Your runtime beats 5.02 % of python3 submissions
# Your memory usage beats 11.11 % of python3 submissions (15.4 MB)
import statistics
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
med= statistics.median(nums)
l, m, r=0, 0, len(nums) - 1
while m<=r:
m_ind=self.A(m,nums)
if nums[m_ind]>med:
l_ind=self.A(l,nums)
nums[l_ind],nums[m_ind]=nums[m_ind],nums[l_ind]
l+=1
m+=1
elif nums[m_ind]<med:
r_ind=self.A(r,nums)
nums[m_ind],nums[r_ind]=nums[r_ind],nums[m_ind]
r-=1
else:
m+=1
def A(self,i,nums):
n=len(nums)
return(1+2*(i)) % (n|1)
# 44/44 cases passed (228 ms)
# Your runtime beats 25.71 % of python3 submissions
# Your memory usage beats 11.11 % of python3 submissions (15.9 MB)