leetcode刷题笔记324题 摆动排序 II

地址：324. 摆动排序 II

问题描述：

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。

进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

object Solution {
    def wiggleSort(nums: Array[Int]): Unit = {
        val length = nums.length

        //本地交换数组内容
        def swap(nums: Array[Int], i: Int, j: Int): Unit = {
            val temp = nums(i)
            nums(i) = nums(j)
            nums(j) = temp
        }

        //快速选择 获取中位数
        //只需对一侧递归 对于本题而言 另一侧需要处理
        def quickSelect(nums: Array[Int], left: Int, right: Int, dest: Int): Unit = {
            //if (left == right || nums.length == 2) return
            val povit = right
            var i = left
            var j = left
            
            while (j < right) {
                if (nums(j) > nums(povit)) j += 1
                else {
                    swap(nums, i, j)
                    i += 1
                    j += 1
                }
            }
            swap(nums, i, povit)
            
            val k = i - left + 1
            
            if (dest == i) return
            else if (dest < i) quickSelect(nums, left, i-1, dest)
            else quickSelect(nums, i+1, right, dest-i-1)
        }

        //荷兰国旗问题
        //将快速选择的结果（含一侧不确定）分为三部分， 即小于中位数， 等于中位数， 大于中位数三个部分
        def partition(nums: Array[Int], iLeft: Int, iRight: Int, midVal: Int): Unit = {
            var left = iLeft 
            var right = iRight
            var cur = iLeft

            while (cur < right) {
                if (nums(cur) > midVal) {
                    swap(nums, cur, right)
                    right -= 1
                } else if (nums(cur) < midVal) {
                    swap(nums, left, cur)
                    cur += 1
                    left += 1
                } else {
                    cur += 1
                }
            }

        }

       
        quickSelect(nums, 0, length-1, length/2-1)
        val mid = nums(length/2)
        partition(nums, 0, length-1, mid)

        //处理数组 前半部分倒序插入奇数位 后半部分插入偶数位
        val temp = new Array[Int](nums.size)
        Array.copy(nums, 0, temp, 0, nums.size)
        val k = length/2 - 1
        
        if (length % 2 == 0){
            for (i <- 0 to k) {
            nums(2 * i) = temp(k-i)
            nums(2 * i + 1) = temp(length-1-i)
            }
        } else {
            for (i <- 0 to k) {
            nums(2 * i) = temp(k-i+1)
            nums(2 * i + 1) = temp(length-1-i)
            }
        
            if (length % 2== 1) nums(length-1) = temp(0)
        }
        

    }
}

import "fmt"

func wiggleSort(nums []int)  {
    quickSelect(nums,(len(nums)-1)/2)
    //fmt.Printf("nums: %v\n", nums)
    mid := nums[(len(nums)-1)/2]
    partition(nums, mid)
    //fmt.Printf("nums: %v\n", nums)

    tempArr := make([]int, len(nums))
    copy(tempArr, nums)

    k := len(nums)/2 - 1
    if len(nums)%2 == 0 {
        for i := 0; i <= k; i++ {
            nums[2*i]  = tempArr[k-i]
            nums[2*i+1] = tempArr[len(nums)-1-i] 
        }
    } else {
        for i := 0; i <= k; i++ {
            nums[2*i] = tempArr[k-i+1]
            nums[2*i+1] = tempArr[len(nums)-1-i]
        }
        nums[len(nums)-1] = tempArr[0]
    }
}


func partition(nums []int, val int) {
    i, j, k := 0, 0, len(nums)-1
    for (j <  k) {
        if nums[j] > val {
            swap(nums, j, k)
            k -= 1
        } else if nums[j] < val {
            swap(nums, j, i)
            i += 1
            j += 1
        } else {
            j += 1
        }
    }
}

func quickSelect(nums []int, dest int) {
    //if len(nums) == 1 || len(nums) == 2 { return }
    pivot := len(nums)-1
    i := 0
    j := 0

    for (j < len(nums)-1) {
        if nums[j] >= nums[pivot] { 
            j += 1
        } else {
            swap(nums , i, j)
            i += 1
            j += 1
        } 
    }
    swap(nums, i, pivot)

    if i == dest {
        return 
    } else if  i > dest {
        quickSelect(nums[:i], dest)
    } else {
        quickSelect(nums[i+1:], dest-i-1)
    }
}

func swap(nums []int, i int, j int) {
    temp :=  nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}