905. 按奇偶排序数组

Posted on | In
Words count in article: 732 | Reading time ≈ 3

题目

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

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

示例1:

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

示例2：

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

提醒:

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

解法

解法一：

遍历一次，用两个位置索引，初始化为0，和数组长度减1。分别判断它们对应位子上的数，是奇数还是偶数。如果前一个位置是奇数，后一个是偶数，则对应位置的数互换，否则前一个位置的索引自增，后一个位置的索引自减，直到双方相遇为止。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] sortArrayByParity(int[] A) {
		int i = 0;
		int j = A.length - 1;

		while (i < j) {
			if (A[i] % 2 == 0) {
				i++;
			} else if (A[j] % 2 == 1) {
				j--;
			}

			if (i < j) {
				int temp = A[i];
				A[i++] = A[j];
				A[j--] = temp;
			}
		}
		return A;
	}

CPP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> sortArrayByParity(vector<int>& A) {
        int i = 0;
        int j = A.size() - 1;

        while (i < j) {
            if (A[i] % 2 == 0) {
                i++;
            } else if (A[j] % 2 == 1) {
                j--;
            }

            if (i < j) {
                int temp = A[i];
                A[i++] = A[j];
                A[j--] = temp;
            }
        }
        return A;
    }

解法二：

遍历一次，但是用一个位置索引。在遍历的过程中，用一个oddIndex 保存当前偶数的位置索引，从0开始。因为题目要求先输出偶数，后输出奇数。然后遍历数组，在遍历的过程中，如果发现当前遍历的数为偶数，则和oddIndex上的值做交换，然后oddIndex自增。

以数组4，2，1，3为例，

数组 oddIndex index 说明
初始化 4，2，1，3 0 0
开始循环，第一步 4，2，1，3 1 1 index为0的位置上为偶数，和oddIndex做交换
第二步 4，2，1，3 2 2 index为1的位置上为偶数，和oddIndex做交换
第三步 4，2，1，3 2 3 没有匹配到偶数

以数组1，2，3，4为例

数组 oddIndex index 说明
初始化 1，2，3，4 0 0
开始循环，第一步 1，2，3，4 0 1 index为0的位置上为奇数，继续
第二步 2，1，3，4 1 2 index为1的位置上为偶数，和oddIndex做交换
第三步 2，1，3，4 1 3 index为2的位置上为奇数，继续
第四步 2，4，3，1 2 4 index3的位置上为奇数，和oddIndex做交换

Java

1
2
3
4
5
6
7
8
9
10
11
12
public int[] sortArrayByParity(int[] A) {
        int oddIndex = 0;
        for(int i = 0; i < A.length ; i++){
            if(A[i] % 2 == 0){
                int temp = A[i];
                A[i] = A[oddIndex];
                A[oddIndex] = temp;
                oddIndex++;
            }
        }
        return A;
    }

CPP

1
2
3
4
5
6
7
8
9
10
11
12
13
string defangIPaddr(string address) {
        string s="";
        string str="[.]";
        for(int i = 0;i < address.size();i++) {
            char c = address[i];
            if(address[i] == '.') {
                s.append(str);
            } else {
                s += c;
            }
        }
        return s;
    }
0%