- 当前位置：首页 >IT科技类资讯 >数据结构与算法之按奇偶排序数组II
数据结构与算法之按奇偶排序数组II
发布时间：2025-11-05 01:05:06 来源：云智核 作者：域名
一道简单模拟题，数据算法数组来做做看!
按奇偶排序数组II
力扣题目链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii/
给定一个非负整数数组 A，结构 A 中一半整数是奇偶奇数，一半整数是排序偶数。
对数组进行排序，数据算法数组以便当 A[i] 为奇数时，结构i 也是奇偶奇数;当 A[i] 为偶数时， i 也是排序偶数。
你可以返回任何满足上述条件的数据算法数组数组作为答案。
示例：
输入：[4,结构2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,奇偶5,4,7]，[2,排序7,4,5] 也会被接受。思路
这道题目直接的数据算法数组想法可能是两层for循环再加上used数组表示使用过的源码库元素。这样的结构的时间复杂度是O(n^2)。
方法一
其实这道题可以用很朴实的奇偶方法，时间复杂度就就是O(n)了，C++代码如下：
class Solution { public: vector<int> sortArrayByParityII(vector<int>& A) { vector<int> even(A.size() / 2); // 初始化就确定数组大小，节省开销 vector<int> odd(A.size() / 2); vector<int> result(A.size()); int evenIndex = 0; int oddIndex = 0; int resultIndex = 0; // 把A数组放进偶数数组，和奇数数组 for (int i = 0; i < A.size(); i++) { if (A[i] % 2 == 0) even[evenIndex++] = A[i]; else odd[oddIndex++] = A[i]; } // 把偶数数组，奇数数组分别放进result数组中 for (int i = 0; i < evenIndex; i++) { result[resultIndex++] = even[i]; result[resultIndex++] = odd[i]; } return result; } }; 时间复杂度：O(n) 空间复杂度：O(n)方法二
以上代码我是建了两个辅助数组，而且A数组还相当于遍历了两次，用辅助数组的好处就是思路清晰，优化一下就是香港云服务器不用这两个辅助树，代码如下：
class Solution { public: vector<int> sortArrayByParityII(vector<int>& A) { vector<int> result(A.size()); int evenIndex = 0; // 偶数下表 int oddIndex = 1; // 奇数下表 for (int i = 0; i < A.size(); i++) { if (A[i] % 2 == 0) { result[evenIndex] = A[i]; evenIndex += 2; } else { result[oddIndex] = A[i]; oddIndex += 2; } } return result; } }; 时间复杂度O(n) 空间复杂度O(n)方法三
当然还可以在原数组上修改，连result数组都不用了。
class Solution { public: vector<int> sortArrayByParityII(vector<int>& A) { int oddIndex = 1; for (int i = 0; i < A.size(); i += 2) { if (A[i] % 2 == 1) { // 在偶数位遇到了奇数 while(A[oddIndex] % 2 != 0) oddIndex += 2; // 在奇数位找一个偶数 swap(A[i], A[oddIndex]); // 替换 } } return A; } }; 时间复杂度：O(n) 空间复杂度：O(1)这里时间复杂度并不是O(n^2)，因为偶数位和奇数位都只操作一次，不是n/2 * n/2的关系，而是n/2 + n/2的关系!
其他语言版本
Java
// 方法一 class Solution { public int[] sortArrayByParityII(int[] nums) { // 分别存放 nums 中的奇数、偶数 int len = nums.length; int evenIndex = 0; int oddIndex = 0; int[] even = new int[len / 2]; int[] odd = new int[len / 2]; for (int i = 0; i < len; i++) { if (nums[i] % 2 == 0) { even[evenIndex++] = nums[i]; } else { odd[oddIndex++] = nums[i]; } } // 把奇偶数组重新存回 nums int index = 0; for (int i = 0; i < even.length; i++) { nums[index++] = even[i]; nums[index++] = odd[i]; } return nums; } }Python3
#方法2 class Solution: def sortArrayByParityII(self, nums: List[int]) -> List[int]: result = [0]*len(nums) evenIndex = 0 oddIndex = 1 for i in range(len(nums)): if nums[i] % 2: #奇数 result[oddIndex] = nums[i] oddIndex += 2 else: #偶数 result[evenIndex] = nums[i] evenIndex += 2 return result #方法3 class Solution: def sortArrayByParityII(self, nums: List[int]) -> List[int]: oddIndex = 1 for i in range(0,len(nums),2): #步长为2 if nums[i] % 2: #偶数位遇到奇数 while nums[oddIndex] % 2: #奇数位找偶数 oddIndex += 2 nums[i], nums[oddIndex] = nums[oddIndex], nums[i] return numsGo
// 方法一 func sortArrayByParityII(nums []int) []int { // 分别存放 nums 中的奇数、偶数 even, odd := []int{}, []int{} for i := 0; i < len(nums); i++ { if (nums[i] % 2 == 0) { even = append(even, nums[i]) } else { odd = append(odd, nums[i]) } } // 把奇偶数组重新存回 nums result := make([]int, len(nums)) index := 0 for i := 0; i < len(even); i++ { result[index] = even[i]; index++; result[index] = odd[i]; index++; } return result; }JavaScript
//方法一 var sortArrayByParityII = function(nums) { const n = nums.length; // 分别存放 nums 中的奇数、偶数 let evenIndex = 0, oddIndex = 0; // 初始化就确定数组大小，节省开销 const even = new Array(Math.floor(n/2)); const odd = new Array(Math.floor(n/2)); // 把A数组放进偶数数组，免费源码下载和奇数数组 for(let i = 0; i < n; i++){ if(nums[i] % 2 === 0) even[evenIndex++] = nums[i]; else odd[oddIndex++] = nums[i]; } // 把奇偶数组重新存回 nums let index = 0; for(let i = 0; i < even.length; i++){ nums[index++] = even[i]; nums[index++] = odd[i]; } return nums; }; //方法二 var sortArrayByParityII = function(nums) { const n = nums.length; const result = new Array(n); // 偶数下标 和 奇数下标 let evenIndex = 0, oddIndex = 1; for(let i = 0; i < n; i++){ if(nums[i] % 2 === 0) { result[evenIndex] = nums[i]; evenIndex += 2; } else { result[oddIndex] = nums[i]; oddIndex += 2; } } return result; }; //方法三 var sortArrayByParityII = function(nums) { let oddIndex = 1; for(let i = 0; i < nums.length; i += 2){ if(nums[i] % 2 === 1){ // 在偶数位遇到了奇数 while(nums[oddIndex] % 2 !== 0) oddIndex += 2;// 在奇数位找一个偶数 [nums[oddIndex], nums[i]] = [nums[i], nums[oddIndex]]; // 解构赋值交换 } } return nums; };源码下载IT资讯网IT技术网益华科技亿华云企商汇源码库服务器租用香港云服务器多维IT资讯益强编程堂亿华云益强前沿资讯益华科技益强IT技术网编程之道云智核码上建站技术快报亿华科技亿华智造益强科技创站工坊益强智囊团益强科技运维纵横益强编程舍亿华云计算科技前瞻智能时代亿华互联码力社思维库全栈开发IT资讯网益强数据堂益华科技益强智未来极客码头汇智坊益华IT技术论坛
- Copyright © 2025 Powered by 数据结构与算法之按奇偶排序数组II,云智核 滇ICP备2023006006号-28sitemap