奇数位上都是奇数偶数位上都是偶数

末蓝、 2022-07-16 00:23 200阅读 0赞

牛客OJ，最近帮做笔试的一道题。

## 原题 ##

[http://www.nowcoder.com/questionTerminal/b89b14a3b5a94e438b518311c5156366?from=14pdf][http_www.nowcoder.com_questionTerminal_b89b14a3b5a94e438b518311c5156366_from_14pdf]

给定一个长度不小于2的数组arr。 写一个函数调整arr，使arr中要么所有的偶数位上都是偶数，要么所有的奇数位上都是奇数上。 要求：如果数组长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1),下标0,2,4,6…算作偶数位,下标1,3,5,7…算作奇数位，例如\[1,2,3,4\]调整为\[2,1,4,3\]即可

--------------------

## 分析 ##

牛客上面也有解析了，我也记录分享一蛤。

题目要求是奇数位上都是奇数，或者偶数位上都是偶数。理想情况下，奇偶对半，这样奇数在奇数位上，偶数在偶数位上。一般情况下，要么奇数多，则奇数填满奇数位后，肯定在偶数位上也有；，同理，偶数多的情况。

因此，这个题目的思路就是，一次遍历，两个指针或索引分别指向奇数位和偶数位，只要发现不符合就交换。

#include <iostream>
    #include <vector>
    using namespace std;
    
    void Adjust( vector<int>& arr);
    void printArray( vector<int>& arr);
    bool isEven(int &num);
    void swap(int &a,int &b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
    
    int main()
    {
        int a[]={
       1,2,3,4};
        vector<int>arr(a,a+4);
        printArray(arr);
        Adjust(arr);
        printArray(arr);
        return 0;
    }
    
    
    void printArray(vector<int>&arr)
    {
        int i;
        for(i=0;i<arr.size();i++)
        {
            cout << arr[i]<< " ";
        }
        cout << endl;
    }
    
    void Adjust(vector<int>&arr)
    {
        int oddCount=1;
        int evenCount=0;
        int n=arr.size();
        int i;
        while(oddCount<n &&evenCount<n)
        {
            //如果没有问题就往上累加。
            while(evenCount<n&&isEven(arr[evenCount]))
                evenCount+=2;
            while(oddCount<n&&!isEven(arr[oddCount]) )
                oddCount+=2;
    
            //跳出循环说明两者至少有一个不满足，或者已经便利完成。
            //这样一交换肯定会满足一方。
            if(evenCount < n && oddCount<n)
            {
                swap(arr[evenCount],arr[oddCount]);
            }
        }
        return;
    }
    
    bool isEven(int &num)
    {
        return num%2==0?true:false;
    }

[http_www.nowcoder.com_questionTerminal_b89b14a3b5a94e438b518311c5156366_from_14pdf]: http://www.nowcoder.com/questionTerminal/b89b14a3b5a94e438b518311c5156366?from=14pdf