已知数组A[n]中的元素为整型，设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数，要求时间复杂度为O(n)

一般这种要求时间复杂度的，采取的策略为用空间换时间

代码：

#include <iostream>

using namespace std;
int* Ajust(int a[], int n) {
    int* res = new int[n];
    int* even = new int[n];
    int* odd = new int[n];
    int index = 0, even_index = 0, odd_index = 0;
    int i, j;
    for(i = 0; i < n; i++) {
        if(a[i] % 2 == 0) {
            even[even_index++] = a[i];
        } else {
            odd[odd_index++] = a[i];
        }
    }
    i = j = 0;
    while(i < odd_index) {
        res[index++] = odd[i++];
    }
    while(j < even_index) {
        res[index++] = even[j++];
    }
    return res;
}

int main() {
    int a[6] = {1, 3, 2, 4, 8, 6};
    int *res = Ajust(a, 6);
    for( int i = 0; i < 6; i++)
        cout << res[i] << " ";
    return 0;
}

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_39993896/article/details/78841210
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2023-01-02 08:35:06
阅读 ( 179 )
分类：算法

已知数组A[n]中的元素为整型，设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数，要求时间复杂度为O(n)

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看