0324. Wiggle Sort I I

324. Wiggle Sort II #

题目 #

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?

题目大意 #

给定一个数组,要求给它进行“摆动排序”,“摆动排序”即:nums[0] < nums[1] > nums[2] < nums[3]…

解题思路 #

这一题最直接的方法是先排序,然后用 2 个指针,一个指向下标为 0 的位置,另一个指向下标为 n/2 的位置。最终的数组的奇数位从下标为 0 开始往后取,偶数位从下标为 n/2 中间位置开始往后取。这种方法时间复杂度为 O(n log n)。

题目要求用时间复杂度 O(n) 和 空间复杂度 O(1) 的方法解决。思路如下,先找到数组中间大小的数字,然后把数组分为 2 部分:

Index :       0   1   2   3   4   5
Small half:   M       S       S    
Large half:       L       L       L(M)

奇数位排中间数和小于中间数的数字,偶数位排大于中间数的数字和中间数。如果中间数字有多个,那么偶数位最后几位也是中间数,奇数位开头的前几位也是中间数。

举例,给定一个数组如下,中间数是 5 。有 2 个 5 。

13   6   5   5   4   2

         M
Step 1: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
             Left
              i
                                      Right

nums[Mapped_idx[i]] = nums[1] = 6 > 5, 所以可以把 6 放在第 1 个奇数位的位置。left 和 i 同时右移。

Step 2: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
                  Left
                   i
                                      Right

nums[3] = 5 = 5, 5 可以放在下标为 3 的位置,由于 5 已经和中间数相等了,所以只后移 i 。

Step 3: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
                  Left
                        i
                                     Right

nums[5] = 2 < 5, 因为比中位数小,所以应该放在偶数位的最后 1 位。这里的例子而言,应该放在下标为 4 的位置上。交换 nums[Mapped_idx[i]] 和 nums[Mapped_idx[Right]],交换完成以后 right 向左移。

Step 4: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    2    4 
                  Left
                        i
                               Right

nums[5] = 4 < 5, 因为比中位数小,所以应该放在偶数位的当前倒数第一位。这里的例子而言,应该放在下标为 2 的位置上。交换 nums[Mapped_idx[i]] 和 nums[Mapped_idx[Right]],交换完成以后 right 向左移。

Step 5: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    4    5    2    5 
                  Left
                        i
                            Right

nums[5] = 5 = 5, 由于 5 已经和中间数相等了,所以只后移 i 。

Step 6: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    4    5    2    5 
                  Left
                             i
                            Right

nums[0] = 13 > 5, 由于 13 比中位数大,所以可以把 13 放在第 2 个奇数位的位置,并移动 left 和 i 。

Step Final: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        5    6    4    13   2    5 
                      Left
                                  i
                            Right

i > Right, 退出循环,最终摆动排序的结果是 5 6 4 13 2 5 。

具体时间见代码,时间复杂度 O(n) 和 空间复杂度 O(1)。

代码 #


package leetcode

import (
	"sort"
)

// 解法一
func wiggleSort(nums []int) {
	if len(nums) < 2 {
		return
	}
	median := findKthLargest324(nums, (len(nums)+1)/2)
	n, i, left, right := len(nums), 0, 0, len(nums)-1

	for i <= right {
		if nums[indexMap(i, n)] > median {
			nums[indexMap(left, n)], nums[indexMap(i, n)] = nums[indexMap(i, n)], nums[indexMap(left, n)]
			left++
			i++
		} else if nums[indexMap(i, n)] < median {
			nums[indexMap(right, n)], nums[indexMap(i, n)] = nums[indexMap(i, n)], nums[indexMap(right, n)]
			right--
		} else {
			i++
		}
	}
}

func indexMap(index, n int) int {
	return (1 + 2*index) % (n | 1)
}

func findKthLargest324(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	return selection324(nums, 0, len(nums)-1, len(nums)-k)
}

func selection324(arr []int, l, r, k int) int {
	if l == r {
		return arr[l]
	}
	p := partition324(arr, l, r)

	if k == p {
		return arr[p]
	} else if k < p {
		return selection324(arr, l, p-1, k)
	} else {
		return selection324(arr, p+1, r, k)
	}
}

func partition324(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}

// 解法二
func wiggleSort1(nums []int) {
	if len(nums) < 2 {
		return
	}
	array := make([]int, len(nums))
	copy(array, nums)
	sort.Ints(array)
	n := len(nums)
	left := (n+1)/2 - 1 // median index
	right := n - 1      // largest value index
	for i := 0; i < len(nums); i++ {
		// copy large values on odd indexes
		if i%2 == 1 {
			nums[i] = array[right]
			right--
		} else { // copy values decremeting from median on even indexes
			nums[i] = array[left]
			left--
		}
	}
}


⬅️上一页

下一页➡️

Calendar Apr 17, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者