【LeetCode每日一题】——905.按奇偶排序数组

一【题目类别】

• 排序

二【题目难度】

• 简单

三【题目编号】

• 905.按奇偶排序数组

四【题目描述】

• 给你一个整数数组 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$

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为数组的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package Sort;

import java.util.Arrays;

/**
 * @Author: IronmanJay
 * @Description: 905.按奇偶排序数组
 * @CreateTime: 2022-11-14  09:04
 */
public class p905_SortArrayByParity {

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 4};
        int[] res = sortArrayByParity(nums);
        System.out.println("res = " + Arrays.toString(nums));
    }

    public static int[] sortArrayByParity(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 != 0) {
                right--;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2. C语言版

#include

int* sortArrayByParity(int* nums, int numsSize, int* returnSize)
{
	int left = 0;
	int right = numsSize - 1;
	while (left < right)
	{
		while (left < right && nums[left] % 2 == 0)
		{
			left++;
		}
		while (left < right && nums[right] % 2 != 0)
		{
			right--;
		}
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
	}
	*returnSize = numsSize;
	return nums;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

十【提交结果】

1. Java语言版
   

2. C语言版