Sort

75. Sort Colors

class Solution {
    //inplace two pass (2n)
    public void sortColors(int[] nums) {
        if (nums==null||nums.length<2) return;
        int red = 0, white = 0, blue = 0;
        for (int i : nums) {
            if (i==0) red++;
            else if (i==1) white++;
            else blue++;
        }
        for (int i = 0; i<nums.length; i++) {
            if (red>0) {
                nums[i]=0;
                red--;
            }else if (white>0) {
                nums[i]=1;
                white--;
            }else {
                nums[i]=2;
                blue--;
            }
        }
    }
}

improve:

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (nums==null||len<2) return;
        int left=0, right=len-1, index=0;
        while (index<=right) {
            if (nums[index]==2) swap(nums, index, right--);
            else if (nums[index]==0) swap(nums, left++, index++);
            else if (nums[index]==1) index++;
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

280. Wiggle Sort

class Solution {
    //nlogn + n
    public void wiggleSort(int[] nums) {
        int len=nums.length;
        if(nums==null||len<2) return;
        Arrays.sort(nums);
        for (int i =2; i<len; i+=2){
            swap(nums, i, i-1);
        }
    }
    private void swap(int[] nums, int p1, int p2) {
        int temp=nums[p1];
        nums[p1]=nums[p2];
        nums[p2]=temp;
    }
}

class Solution {
    public void wiggleSort(int[] nums) {
        int len=nums.length;
        if(nums==null||len<2) return;
        for (int i=1; i<len; i++){
            if(i%2==1 && nums[i]<nums[i-1] || i%2==0 && nums[i]>nums[i-1])
                swap(nums, i, i-1);
        }
    }
    private void swap(int[] nums, int p1, int p2) {
        int temp=nums[p1];
        nums[p1]=nums[p2];
        nums[p2]=temp;
    }
}

56. Merge Intervals

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length < 2) return true;
        Comparator<Interval> comparator = new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        };
        Arrays.sort(intervals, comparator);
        // 不知道为什么，比直接写Arrays.sort(intervals, (a, b) -> a.start - b.start); 要快
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < intervals[i-1].end) return false;
        }
        return true;
    }
}