题目描述

解题思路

归并排序

public int search(int[] nums, int target) {
    int i = 0;
    for (i = 1; i < nums.length; i++)
        if (nums[i] < nums[i - 1]) break;
    // 分两部分进行二分
    int left = search(nums, 0, i, target);
    if (left != -1) return left;
    int right = search(nums, i + 1, nums.length - 1, target);
    if (right != -1) return right;
    return -1;
}
public int search(int[] nums, int left, int right, int target) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] == target) return mid;
    }
    return -1;
}

时间复杂度过大O(nlogn)

单指针

https://leetcode.cn/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
第一次遍历，当遇到0之后，将所有0交换在最前面，第二遍遍历把所有1放在0之后。

// 单指针（2次遍历）
public void sortColors(int[] nums) {
    int n = nums.length, ptr = 0;
    // 将0放在前面
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            int temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ptr++;
        }
    }
    // 将1放在0的后面
    for (int i = ptr; i < nums.length; i++) {
        if (nums[i] == 1) {
            int temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ptr++;
        }
    }
}

双指针

https://leetcode.cn/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
单指针优化为双指针：
遇到1，就交换在p1位置，p1加一。
如果遇到0，此时会发现如果和p0交换0，但是此时1已经放在了这个位置，所以此时就把1给交换过去了，所以我们还要把交换出去的1再和p1交换，所以交换2次之后p1，p0都加一。

public void sortColors(int[] nums) {
    int n = nums.length, p1 = 0, p0 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 1) {
            int temp = nums[i];
            nums[i] = nums[p1];
            nums[p1] = temp;
            p1++;
        }
        else if (nums[i] == 0) {
            int temp = nums[i];
            nums[i] = nums[p0];
            nums[p0] = temp;
            // 此时交换出去的一定是1，所以需要把1交换在p1位置
            if (p0 < p1) {
                temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
            }
            p0++;
            p1++;
        }
    }
}