905.按奇偶排序数组

LeetCode LeetCode 数组双指针排序

发布时间 : 2000-01-10 09:00

字数:1.9k 阅读 :

评论:

905.按奇偶排序数组

905.按奇偶排序数组

905.1 题目

给你一个整数数组 nums，将 nums 中的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的任一数组作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

提示：

1 <= nums.length <= 5000
0 <= nums[i] <= 5000

905.2 题解

方法一：双指针

思路

用左右双指针从两端向中间扫描：

左指针找奇数（需要移到后面）
右指针找偶数（需要移到前面）
找到后交换

举个例子：nums = [3,1,2,4]

left=0(3奇数), right=3(4偶数)：交换 → [4,1,2,3]
left=1(1奇数), right=2(2偶数)：交换 → [4,2,1,3]
left=2, right=1，循环结束
结果：[4,2,1,3]，偶数在前，奇数在后 ✓

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)，原地交换

代码

// 方法一：双指针
// 使用双指针分别从数组头尾向中间移动，交换偶数和奇数位置的元素。
static int[] MoveEvenOdd1(int[] nums)
{
    // 左指针初始化为数组头部
    int left = 0;
    // 右指针初始化为数组尾部
    int right = nums.Length - 1;

    // 循环直到左指针不再小于右指针
    while (left < right)
    {
        // 左指针找到奇数位置
        while (left < right && nums[left] % 2 == 0)
            left++;

        // 右指针找到偶数位置
        while (left < right && nums[right] % 2 == 1)
            right--;

        // 交换偶数和奇数位置的元素
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;

        // 移动指针，继续寻找下一对需要交换的元素
        left++;
        right--;
    }

    // 返回原数组，其中偶数和奇数位置已经被正确交换
    return nums;
}

方法二：使用额外数组

思路

创建两个数组分别存储偶数和奇数，遍历原数组，将偶数放入偶数数组，奇数放入奇数数组，最后将偶数数组和奇数数组合并回原数组。

空间换时间，代码直观易懂。

举个例子：nums = [3,1,2,4]

偶数数组：[2,4]
奇数数组：[3,1]
合并：[2,4,3,1]

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

代码

// 方法二：使用额外数组
// 遍历原数组，将偶数和奇数分别存储到两个不同的数组，然后合并数组。
static int[] MoveEvenOdd2(int[] nums)
{
    // 创建两个额外的数组，用于存储偶数和奇数
    int[] evenArray = new int[nums.Length];
    int[] oddArray = new int[nums.Length];

    // 分别记录偶数和奇数数组的当前索引
    int evenIndex = 0;
    int oddIndex = 0;

    // 遍历原数组中的每个元素
    foreach (int num in nums)
    {
        // 如果当前元素是偶数，存储到偶数数组
        if (num % 2 == 0)
            evenArray[evenIndex++] = num;
        // 如果当前元素是奇数，存储到奇数数组
        else
            oddArray[oddIndex++] = num;
    }

    // 合并数组
    for (int i = 0; i < evenIndex; i++)
    {
        nums[i] = evenArray[i];
    }

    for (int i = 0; i < oddIndex; i++)
    {
        nums[evenIndex + i] = oddArray[i];
    }

    // 返回原数组，其中偶数和奇数已经被分别存储并合并
    return nums;
}

方法三：遍历发现偶数交换

思路

维护一个指针 evenIndex 指向当前偶数应该放置的位置，遍历数组，发现偶数就交换到 evenIndex 位置。

原地操作，只使用常数额外空间。

举个例子：nums = [3,1,2,4]

evenIndex=0, allIndex=0：3是奇数，不交换
evenIndex=0, allIndex=1：1是奇数，不交换
evenIndex=0, allIndex=2：2是偶数，交换到位置0，nums=[2,1,3,4]
evenIndex=1, allIndex=3：4是偶数，交换到位置1，nums=[2,4,3,1]

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

代码

// 方法三：遍历发现偶数交换
static int[] MoveEvenOdd3(int[] nums)
{
    int allIndex = 0;
    int evenIndex = -1;
    while (allIndex <= nums.Length - 1)
    {
        if (nums[allIndex] % 2 == 0)
        {
            evenIndex++;
            (nums[allIndex], nums[evenIndex]) = (nums[evenIndex], nums[allIndex]);
        }
        allIndex++;
    }

    return nums;
}

905.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个整数数组 nums，将 nums 中的所有偶数元素移动到数组的前面，后跟所有奇数元素。
        // 返回满足此条件的 任一数组 作为答案。

        // 示例 1：
        // 输入：nums = [3,1,2,4]
        // 输出：[2,4,3,1]
        // 解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

        // 示例 2：
        // 输入：nums = [0]
        // 输出：[0]

        // 提示：
        // 1 <= nums.length <= 5000
        // 0 <= nums[i] <= 5000

        #endregion

        #region 测试

        // 示例 1（各方法用独立数组，避免双指针解法打乱顺序后影响另一解法演示）
        int[] nums1a = { 3, 1, 2, 4 };
        int[] nums1b = { 3, 1, 2, 4 };
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(", ", MoveEvenOdd1(nums1a))}]");
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(", ", MoveEvenOdd2(nums1b))}]");
        int[] nums1c = { 3, 1, 2, 4 };
        Console.WriteLine($"示例1 方法3 输出：[{string.Join(", ", MoveEvenOdd3(nums1c))}]");

        // 示例 2
        int[] nums2a = { 0 };
        int[] nums2b = { 0 };
        int[] nums2c = { 0 };
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(", ", MoveEvenOdd1(nums2a))}]");
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(", ", MoveEvenOdd2(nums2b))}]");
        Console.WriteLine($"示例2 方法3 输出：[{string.Join(", ", MoveEvenOdd3(nums2c))}]");

        #endregion
    }

    #region 答案

    // 方法一：双指针
    // 使用双指针分别从数组头尾向中间移动，交换偶数和奇数位置的元素。
    static int[] MoveEvenOdd1(int[] nums)
    {
        // 左指针初始化为数组头部
        int left = 0;
        // 右指针初始化为数组尾部
        int right = nums.Length - 1;

        // 循环直到左指针不再小于右指针
        while (left < right)
        {
            // 左指针找到奇数位置
            while (left < right && nums[left] % 2 == 0)
                left++;

            // 右指针找到偶数位置
            while (left < right && nums[right] % 2 == 1)
                right--;

            // 交换偶数和奇数位置的元素
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            // 移动指针，继续寻找下一对需要交换的元素
            left++;
            right--;
        }

        // 返回原数组，其中偶数和奇数位置已经被正确交换
        return nums;
    }

    // 方法二：使用额外数组
    // 遍历原数组，将偶数和奇数分别存储到两个不同的数组，然后合并数组。
    static int[] MoveEvenOdd2(int[] nums)
    {
        // 创建两个额外的数组，用于存储偶数和奇数
        int[] evenArray = new int[nums.Length];
        int[] oddArray = new int[nums.Length];

        // 分别记录偶数和奇数数组的当前索引
        int evenIndex = 0;
        int oddIndex = 0;

        // 遍历原数组中的每个元素
        foreach (int num in nums)
        {
            // 如果当前元素是偶数，存储到偶数数组
            if (num % 2 == 0)
                evenArray[evenIndex++] = num;
            // 如果当前元素是奇数，存储到奇数数组
            else
                oddArray[oddIndex++] = num;
        }

        // 合并数组
        for (int i = 0; i < evenIndex; i++)
        {
            nums[i] = evenArray[i];
        }

        for (int i = 0; i < oddIndex; i++)
        {
            nums[evenIndex + i] = oddArray[i];
        }

        // 返回原数组，其中偶数和奇数已经被分别存储并合并
        return nums;
    }

    // 方法三：遍历发现偶数交换
    static int[] MoveEvenOdd3(int[] nums)
    {
        int allIndex = 0;
        int evenIndex = -1;
        while (allIndex <= nums.Length - 1)
        {
            if (nums[allIndex] % 2 == 0)
            {
                evenIndex++;
                (nums[allIndex], nums[evenIndex]) = (nums[evenIndex], nums[allIndex]);
            }
            allIndex++;
        }

        return nums;
    }

    #endregion
}

905.4 运行结果

示例1 方法1 输出：[4, 2, 1, 3]
示例1 方法2 输出：[2, 4, 3, 1]
示例1 方法3 输出：[2, 4, 3, 1]
示例2 方法1 输出：[0]
示例2 方法2 输出：[0]
示例2 方法3 输出：[0]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com