欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

922. Sort Array By Parity II。

程序员文章站 2024-03-06 09:48:37
...

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

原文链接:https://leetcode.com/problems/sort-array-by-parity-ii/


给定一个数组,其中奇数和偶数各一半,要求返回的数组中,奇数下标中的元素为奇数,偶数索引下标中的元素为偶数。


最简单的做法就是将原数组中的元素进行分开存放,然后再将这些元素按照要求组装起来。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index=0,odd_index=0;
        vector<int> odds,evens;
        for(int i : A) {
            if(i%2 == 0)
                evens.push_back(i);
            else
                odds.push_back(i);
        }
        for(i=0;i<A.size();i++){
            if(i%2==0) {
                A[i] = evens[even_index];
                even_index++;
            } else {
                A[i] = odds[odd_index];
                odd_index++;
            }
        }
        return A;
    }
};

显然上述做法并不明智,既浪费了时间又浪费了空间。我们可以在此基础上优化一下,可以先申请一个与原来数组大小相同的结果数组。遍历原先的数组,如果遇到了奇数元素就将该元素放置到结果数组中的奇数位置上,如果是偶数元素则放置到结果数组中的偶数位置上。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index=0,odd_index=1;
        vector<int> result(A.size(),0);
        for(i=0;i<A.size();i++) {
            if(A[i]%2==0) {//如果当前数字为偶数,则将该数字放到结果数组中的偶数索引上
                result[even_index] = A[i];
                even_index += 2;
            } else {
                result[odd_index] = A[i];
                odd_index += 2;
            }
        }
        return result;
    }
};

可以看到上述两个方法都是O(n)的空间复杂度,那么接下来的优化可以从缩小空间复杂度入手,一个不难想到的做法就是如果当前索引是奇数但是元素不是奇数,那么就找到下一个奇数元素进行交换,偶数也是如此。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index,odd_index;
        for(i=0;i<A.size();i++) {
            even_index = odd_index = i;
            if(i%2 == 0) {//当前为偶数索引
                while(A[even_index]%2!=0 && even_index<A.size()) {//找到下一个偶数
                    even_index++;
                }
                swap(A[i],A[even_index]);
            } else {//当前为奇数索引
                while(A[odd_index]%2==0 && odd_index<A.size()) {//找到下一个奇数
                    odd_index++;
                }
                swap(A[i],A[odd_index]);
            }
        }
        return A;
    }
};

显然上面一个方法,冗余了很多循环。我们可以对奇数索引进行检查,如果是奇数元素的话,就检查下一个奇数索引,直到发现奇数索引上不是奇数元素停止,然后按照此方法检查偶数索引,最后将其进行交换。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int even_index=0,odd_index=1;
        while(even_index<A.size() && odd_index<A.size()) {
            while(A[even_index]%2==0&&even_index<A.size()) even_index+=2;//偶数索引不为偶数时停下来
            while(A[odd_index]%2==1&&odd_index<A.size()) odd_index+=2;//奇数索引不为奇数时停下来
            //cout << A[even_index] << ",index:" << even_index << endl;
            //cout << A[odd_index] << ",index:" << odd_index << endl;
            if(even_index>A.size() || odd_index>A.size()) break;
            swap(A[even_index],A[odd_index]);
        }
        return A;
    }
};

另一种写法:

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) 
    {
        for(int i=0,j=1;i<A.size()&&j<A.size();)
        {
            if(A[i]%2==0)
                i+=2;
            else if(A[j]%2==1)
                j+=2;
            else
                swap(A[i],A[j]);
        }
        return A;
    }
};
相关标签: leetcode 面试