已知顺序表L中的元素为int,请写一时间复杂度O(n)、空间复杂度为O(1)的程序,将L中的奇数元素排在前面,偶数元素排在后面

时间:2024-04-06 19:40:52
Status exchangeEvenOddNumbers(SeqList &S){
    int j = 0,k = 0;
    for(int i = 0;i<=S.last;i++){
        if(S.elem[i]%2 == 1){
            k = S.elem[j];
            S.elem[j] = S.elem[i];
            S.elem[i] = k;
            j++;
        }else{
            continue;
        }
    }
    return OK;
};

算法分析,由于时间复杂度为n,所以只能出现一个for循环;空间复杂度为1,只能使用原有顺序表内存空间;

定义变量 j ,始终记录顺序表中第一个非奇数(也就是第一个偶数呗) 的下标;定义中间变量 k ,临时存储第一个非奇数的值,与查找到的奇数的值进行互换;

整体思路:从头查找,只要查找到奇数,就和第一个非奇数交换位置,因为只有一个 for 循环 , 所以时间复杂度为1;

已知顺序表L中的元素为int,请写一时间复杂度O(n)、空间复杂度为O(1)的程序,将L中的奇数元素排在前面,偶数元素排在后面