面试题 10.11. 峰与谷

在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。

示例:

输入: [5, 3, 1, 2, 3]
输出: [5, 1, 3, 2, 3]
提示：

• nums.length <= 10000

Python 解答：
1.排序

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        arr = sorted(nums)
        i, j, k = 0, len(arr)-1, 0
        flag = 0
        while i <= j:
            if flag:
                nums[k] = arr[i]
                k += 1
                i += 1
            else:
                nums[k] = arr[j]
                k += 1
                j -= 1
            flag = 1- flag

2.特殊性质

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) > 2:
            flag = 1
            i = 1
            while i < len(nums):
                if flag:
                    if nums[i-1] < nums[i]:
                        pass
                    else:
                        nums[i-1], nums[i] = nums[i], nums[i-1]
                else:
                    if nums[i-1] > nums[i]:
                        pass
                    else:
                        nums[i-1], nums[i] = nums[i], nums[i-1]
                i += 1
                flag = 1-flag