LeetCode刷题—双指针解数组排序

前言

双指针分为快慢指针（向一个方向遍历）和左右指针（从两个方向相对遍历）， 在进行数组排序时常用到第一种。

指针 j 用于探路，找到目标元素与指针 i 所指元素交换，并将 i 向前一步，继续。

模板

public int[] sortArrayByParity(int[] A) {
        int i = 0;
        int n = A.length;
    	//j 指针探路
        for(int j = 0; j < n; j++){
            if(找到目标元素){
                //交换
                swap(A, i, j);
                i++;
            }
        }
        return A;
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

905，按奇偶排序数组，easy

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例：

输入：[3,1,2,4]
输出：[2,4,3,1]
（输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。）

题解

此题目标是用 指针j 找到偶数元素，将偶数元素往前提。

代码

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int i = 0;
        int n = A.length;
        for(int j = 0; j < n; j++){
            //找到偶数元素
            if(A[j] % 2 == 0){
                swap(A, i, j);
                i++;
            }
        }
        return A;
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

283，移动 0，easy

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

题解

此题目标是用 指针j 找到非 0 元素，将非 0 元素往前提。

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0;
        for(int j = 0; j < nums.length; j++){
            //找到非 0 元素
            if(nums[j] != 0){
                swap(nums, i, j);
                i++;
            }
        }
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

75，颜色分类，medium

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

题解

与前两题不同在 需要两次交换，先用 指针j 找到 0，将 0 往前提。

再将 j 定于此位置，继续找 1，将 1 往前提。

过程如下：

动画演示

代码

class Solution {
    public void sortColors(int[] nums) {
        int i = 0;
        int n = nums.length;
        //第一步：将 0 往前提
        for(int j = 0; j < n; j++){
            if(nums[j] == 0){
                swap(nums, i, j);
                i++;
            }
        }
        //第二步：将 1 往前提
        for(int j = i; j < n; j++){
            if(nums[j] == 1){
                swap(nums, i, j);
                i++;
            }
        }
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}