按奇偶排序数组（Java+4种方法）

题目

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。

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

方法一：暴力

public int[] sortArrayByParity(int[] A) {
		for (int i = 0; i < A.length; i++) {
			if (A[i] % 2 != 0) {
				// 偶数
				int j = i + 1;
				while (j < A.length && A[j] % 2 != 0) {
					j++;
				}
				if (j < A.length) {
					int temp = A[i];
					A[i] = A[j];
					A[j] = temp;
				}
			}
		}
		return A;
	}

方法二：左右指针

public int[] sortArrayByParity2(int[] A) {
		int left = 0, right = A.length - 1;
		while (left < right) {
			if (A[left] % 2 != 0) {
				// 前面有奇数，从后面拿一个偶数
				while (right > left && A[right] % 2 != 0) {
					right--;
				}
				int temp = A[left];
				A[left] = A[right];
				A[right] = temp;
			}
			left++;
		}
		return A;
}

方法三：排序算法

public int[] sortArrayByParity3(int[] A) {
	Integer[] B = new Integer[A.length];
	for (int i = 0; i < A.length; i++) {
		B[i] = A[i];
	}
	Arrays.sort(B, (a, b) -> Integer.compare(a % 2, b % 2));
	for (int i = 0; i < A.length; i++) {
		A[i] = B[i];
	}
	return A;
}

方法四：两遍扫描

public int[] sortArrayByParity4(int[] A) {
		int[] ans = new int[A.length];
		int index = 0;
		for (int i = 0; i < A.length; i++) {
			if (A[i] % 2 == 0) {
				ans[index++] = A[i];
			}
		}
		for (int i = 0; i < A.length; i++) {
			if (A[i] % 2 != 0) {
				ans[index++] = A[i];
			}
		}
		return ans;
	}

反思

思考！！思考！！认真思考！简单题你可以的
end.

本文地址：https://blog.csdn.net/weixin_44998686/article/details/110292405