[LeetCode] 324. Wiggle Sort II

轉自LeetCode

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

You may assume the input array always has a valid answer.

 

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 5000
• It is guaranteed that there will be an answer for the given input nums.

 

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Solution

這題的想法是，先將 nums 做個 sorting，並存到另一個array

然後用兩個指標，一個從中間開始，一個從最後面開始

然後歷遍array，從中間開始取值回填，然後從後面取值回填，這樣交叉下去

用 [1,5,1,1,6,4] 舉例

sorting 過後，變成 tmp = [1,1,1,4,5,6]，midIndex = 2, lastIndex = 5

i = 0, 從中間取值，nums[0] = 1，midIndex 更新為 1

i = 1，從後面取值，nums[1] = 6 (nums = [1,6])，lastIndex更新為4

i = 2, 從中間取值，nums[2] = 1(nums = [1,6,1])，midIndex 更新為 0

i = 3，從後面取值，nums[3] = 5 (nums = [1,6,1,5])，lastIndex更新為3

i = 4, 從中間取值，nums[4] = 1(nums = [1,6,1,5,1])，midIndex 更新為 -1

i = 5，從後面取值，nums[5] = 4 (nums = [1,6,1,5,1,4])，lastIndex更新為2

kotlin(參考解法)

	class Solution {
	fun wiggleSort(nums: IntArray): Unit {
	val tmp = nums.sorted()
	var mid = nums.lastIndex / 2
	var last = nums.lastIndex
	for(i in nums.indices) {
	nums[i] = if((i and 1) == 0) tmp[mid--] else tmp[last--]
	}
	}
	}

view raw wiggle_sort_II.kt hosted with ❤ by GitHub

至於題目給的follow up，有點難，目前還沒有想法