LeetCode 324 Wiggle Sort II

Tag: 数组类题目 LeetCode Posted on 2022-03-07 16:20:38 Edited on 2022-03-07 16:20:38 Views: 143

概述

https://leetcode.com/problems/wiggle-sort-ii/

小大小大的排序。

排序法

首先进行排序,之后,把前半段和后半段交替取出元素进行拼接。

注意处理奇数的情况,此时我们手动将其 swap 到最后一个位置。

为了避免靠近中值的值凑到一起,我们还需要倒序访问前半段和后半段。

芜湖,AC:

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int half = nums.size() / 2;
        if (nums.size() % 2) {
            swap(nums[half], nums[nums.size()-1]);
        }
        auto arr = nums;
        for (int i = 0; i < half; i ++) {
            nums[2*i] = arr[half-1-i];
            nums[2*i+1] = arr[half-1-i+half];
        } 
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/