数据结构与算法之按奇偶排序数组II

一道简单模拟题，数据算法数组来做做看!

按奇偶排序数组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 nums 

Go

// 方法一 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; }; 

很赞哦!（92374）