LeetCode Top Interview Questions 324. Wiggle Sort II (Java版; Medium)

曾经终败给现在 2023-07-02 08:28 49阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 324. Wiggle Sort II (Java版; Medium) ##

#### 题目描述 ####

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?

#### 第一次做; 时间复杂度O(N), 空间复杂度O(N)的解法有三个关键步骤:1)找中位数,2)索引映射,3)荷兰国旗:换扩跳,换扩,跳; 超出时间限制41/44 ####

class Solution { 
        public void wiggleSort(int[] nums) { 
            if(nums==null || nums.length==0)
                return;
            //1.找出中位数
            int mid = findMid(nums);
            //3.荷兰国旗
            int n = nums.length, left = -1, right = n, i=0;
            while(i<right){ 
                //换扩跳
                if(nums[newIndex(i,n)] > mid)
                    swap(nums, newIndex(i++,n), newIndex(++left,n));
                //换扩
                else if(nums[newIndex(i,n)] < mid)
                    swap(nums, newIndex(i,n), newIndex(--right,n));
                //跳
                else
                    i++;
            }
            
        }
        //2.坐标映射
        public int newIndex(int i, int n){ 
            return (1+2*i)%(n|1);
        }
        public int findMid(int[] nums){ 
            int n = nums.length;
            int i=-1, mid=(n-1)>>1;
            int left=0, right=n-1;
            while(i!=mid){ 
                if(i>mid){ 
                    i = partition(nums, left, i-1);
                }
                else if(i<mid){ 
                    i = partition(nums, i+1, right);
                }
            }
            return nums[mid];
        }
        //和普通的partition的区别: 大的在前面, 小的在后面
        public int partition(int[] nums, int i, int j){ 
            int pivot = nums[j];
            int big=i-1, small=j, p=i;
            while(p<small){ 
                if(nums[p] >= pivot){ 
                    swap(nums, p++, ++big);
                }
                else{ 
                    swap(nums, p, --small);
                }
            }
            //把pivot放在正确的位置上
            swap(nums, p, j);
            return p;
        }
        public void swap(int[] arr, int i, int j){ 
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

#### 第一次做; 模仿直观的题解解法; 复制一份nums, 排序, 找出中位数, 偶数索引放小于中位数的数, 奇数索引放大于中位数的数; 时间复杂度O(NlogN), 空间复杂度O(N) ####

class Solution { 
        public void wiggleSort(int[] nums) { 
            if(nums==null || nums.length==0)
                return;
            int n = nums.length;
            int[] help = Arrays.copyOf(nums,n);
            Arrays.sort(help);
            int mid = nums[(n-1)>>1], small = (n-1)>>1, big = n-1;
            for(int i=0; i<n; i++){ 
                if(i%2==0)
                    nums[i] = help[small--];
                else
                    nums[i] = help[big--];
            }
        }
    }

#### [题解][Link 1], 虽然不是最优解吧, 但是最朴素直观: 先找到中位数, 把小于中位数的数放到偶数索引上, 把大于中位数的数放到奇数索引上; 时间复杂度O(NlogN), 空间复杂度O(N) ####

public void wiggleSort(int[] nums) { 
            int[] copy = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy);
            
            int n = nums.length;
            int left = (n + 1) / 2 - 1; // median index
            int right = n - 1; // largest value index
            for (int i = 0; i < nums.length; i++)
            {    // copy large values on odd indexes
                if(i%2==1){ 
                    nums[i] = copy[right];
                    right--;
                } else{  // copy values decremeting from median on even indexes
                    nums[i] = copy[left];
                    left--;
                }
            }
        }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode.com/problems/wiggle-sort-ii/discuss/77682/Step-by-step-explanation-of-index-mapping-in-Java