Wiggle Sort & II

Moxmi 发布于2019-08-14 17:18 / 514人阅读

摘要：如果没复杂度的要求，先也可以，再交叉放入数字也可以。交叉的时候注意是按照，降序的。

Wiggle Sort

题目链接：https://leetcode.com/problems...

这道题允许等号，相对简单，有两种方法：1. sort然后交换奇数位和它下一位的元素，2. 不满足条件的时候直接交换

可以用递推来说明一下这么做的正确性：

假设到第i位之前都满足题目要求的关系

现在比较第i位和第i+1位

if i == odd:

nums[i] >= nums[i+1]，到i+1位都满足条件

nums[i] < nums[i+1]，swap(i, i+1)，新的nums[i] >= nums[i+1] >= nums[i-1]，所以到i+1都满足条件

if i == even:

同理

一直递推到len(nums)，所以整个数组都满足条件

public class Solution {
    public void wiggleSort(int[] nums) {
        /* condition: nums[odd] >= nums[even]
         * 1. sort => [1, 2, 3, 4, 5, 6] => swap(i, i+1)
         * 2. swap if a. nums[i] < nums[i+1] i = odd
         *            b. nums[i] > nums[i+1] i = even
         */
        for(int i = 0; i < nums.length - 1; i++) {
            if(i % 2 == 1 && nums[i] < nums[i+1]) swap(nums, i, i+1);
            if(i % 2 == 0 && nums[i] > nums[i+1]) swap(nums, i, i+1);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

324. Wiggle Sort II

题目链接：https://leetcode.com/problems...

这题不能有等号，而且要求O(N)的时间和O(1)的空间，那么感觉只能quick select了。如果没复杂度的要求，先sort也可以，再交叉放入数字也可以。交叉的时候注意是按照[2, 0, 3, 1]，降序的。

public class Solution {
    public void wiggleSort(int[] nums) {
        /* quick select: find the middle element
         * 3 way partitions: [h, l, ...]
         * [2, 0, 3, 1], [2, 0, 3, 1, 4]
         */
         n = nums.length;
         int mid = quickSelect(nums, 0, nums.length - 1, nums.length / 2);
         partition(nums, 0, nums.length - 1, mid);
    }
    
    int n;
    private void partition(int[] nums, int l, int r, int mid) {
        int i = l;
        while(i <= r) {
            if(nums[mapping(i)] > mid) swap(nums, mapping(i++), mapping(l++));
            else if(nums[mapping(i)] < mid) swap(nums, mapping(i), mapping(r--));
            else i++;
            
        }
    }
    
    private int mapping(int i) {
        return (2 * i + 1) % (n | 1);
    }
    
    private int quickSelect(int[] nums, int l, int r, int k) {
        if(l >= r)  return nums[l];
        
        int pivot = nums[r];
        int index = l;
        for(int i = l; i < r; i++) {
            if(nums[i] < pivot) swap(nums, i, index++);
        }
        // swap the pivot to the correct position
        swap(nums, index, r);
        if(index == k) return nums[index];
        else if(index < k) return quickSelect(nums, index + 1, r, k);
        else return quickSelect(nums, l, index - 1, k);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

云服务器 GPU云服务器 Wiggle II sort() sort

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66552.html

[LintCode/LeetCode] Wiggle Sort I &amp; Wiggle Sor

摘要：每隔两位交换一次，如，处理为。难点是会有相等的元素，而要求相邻元素除了外，不能相等。那么就不能取排序后相邻的元素交换，而要和后面的元素交换。例如牺牲空间的做法是，建立一个新数组，按照我们想要的规律放入元素，最后回原数组。 Wiggle Sort Problem Given an unsorted array nums, reorder it in-place such that num...

linkFly 2019-08-14 16:22 评论0 收藏0
[Leetcode] Wiggle Sort 摇摆排序

摘要：就能满足题目要求。代码先将数组排序将数组中一对一对交换交换法复杂度时间空间思路题目对摇摆排序的定义有两部分如果是奇数，如果是偶数，所以我们只要遍历一遍数组，把不符合的情况交换一下就行了。 Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] = nums[i ...

LancerComet 2019-08-14 12:35 评论0 收藏0
[LeetCode] 280. Wiggle Sort

Problem Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { ...

archieyang 2019-08-16 14:00 评论0 收藏0
Meeting Rooms &amp; Meeting Rooms II

摘要：思路这道题就是要找区间之间是否有。而的复杂度是，所以最后总的复杂度为。思路的条件依然是不同的是这题需要求房间数。还是先，指向之前有的最小的那一个。接着的是，比小，所以又放入。。的是，比大，因此出，放入。。 Meeting Rooms Given an array of meeting time intervals consisting of start and end times [[...

TalkingData 2019-08-14 17:11 评论0 收藏0
H-Index &amp; II

H-Index 题目链接：https://leetcode.com/problems... sort： public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; // sort ...

mochixuan 2019-08-14 17:25 评论0 收藏0