905.按奇偶排序数组

LeetCode LeetCode 数组排序双指针

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

字数:1.4k 阅读 :

评论:

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 题解

双指针

// 方法一：双指针
// 使用双指针分别从数组头尾向中间移动，交换偶数和奇数位置的元素。
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;
}

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[] nums1 = { 3, 1, 2, 4 };
        int[] result1_1 = MoveEvenOdd1(nums1);
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(", ", result1_1)}]");
        int[] result1_2 = MoveEvenOdd2(nums1);
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(", ", result1_2)}]");

        // 示例 2
        int[] nums2 = { 0 };
        int[] result2_1 = MoveEvenOdd1(nums2);
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(", ", result2_1)}]");
        int[] result2_2 = MoveEvenOdd2(nums2);
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(", ", result2_2)}]");

        #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 输出：[4, 2, 1, 3]
示例2 方法1 输出：[0]
示例2 方法2 输出：[0]

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