首页 > 试题广场 >

调整数组顺序使奇数位于偶数前面(一)

[编程题]调整数组顺序使奇数位于偶数前面(一)

热度指数：105855 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围： $0 \le n \le 5000$ ，数组中每个数的值 $0 \le val \le 10000$

要求：时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

进阶：时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

示例1

输入

[1,2,3,4]

输出

[1,3,2,4]

示例2

输入

[2,4,6,5,7]

输出

[5,7,2,4,6]

示例3

输入

[1,3,5,6,7]

输出

[1,3,5,7,6]

算法知识视频讲解

三秋叶__

第一次写的好复杂，取出奇数和偶数数组，在把他们合并。下次刷写个排序的0.0
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param array int整型一维数组
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here

    int* arrOdd = NULL;
    int* arrEven = NULL;
    arrOdd = (int*)malloc(sizeof(int) * arrayLen);
    arrEven = (int*)malloc(sizeof(int) * arrayLen);
    if (arrOdd == NULL) {
        // 处理内存分配失败的情况
        return NULL;
    }
    if (arrEven == NULL) {
        // 处理内存分配失败的情况
        return NULL;
    }
    *returnSize = arrayLen;  //指的是返回数组的大小

    int m = 0;
    int n = 0;
    for (int i = 0; i < arrayLen; i++) {
        if (array[i] % 2 != 0) {
            arrOdd[m] = array[i];
            m++;
        } else {
            arrEven[n] = array[i];
            n++;
        }
    }
    for (int i = 0; i < m; i++) {
        array[i] = arrOdd[i];
    }
    for (int i = 0; i < n; i++) {
        array[i + m] = arrEven[i];
    }

    return array;
}

发表于 2024-05-08 10:50:12 回复(0)

小小小孩

void bubble_swap(int* array, int len) 
{
    for(int i=len-2;i>=0;i--)
    {
        for(int j=i;j<len-1;j++)
        {
            if(array[j]%2==0 && array[j+1]%2!=0)
            {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    *returnSize = 0;
    if(array == NULL || arrayLen == 0)
        return NULL;
    bubble_swap(array,arrayLen);
    *returnSize = arrayLen;
    return array;

}

发表于 2023-05-29 01:54:49 回复(0)

李顺利plus

进阶一步到位
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int temp;
    for(int i=0;i<arrayLen;i++){
        if(i<0) i=0;
        if(array[i]%2==0){
            if(i==arrayLen) break;    //若已排查到最后一个仍为偶数，则表明替换完成
            if(array[i+1]%2==1){      //若当前为偶数，但是下一个为奇数，则二者交换
                temp=array[i];
                array[i]=array[i+1];
                array[i+1]=temp;
                i=i-2;                //把指针放到刚才替换的这个偶数的前一个，解决连着都是偶数的情况
            }
        }
    }
    *returnSize=arrayLen;
    return array;
}

发表于 2022-09-28 11:16:47 回复(0)

Duoni

typedef struct SL//定义一个结构体模板
{
    int* vate;//int指针/数组
    int size;//实际数位计数
    int capecity;//空间大小
}SL;

void init(SL* tr)//初始化
{
    tr->vate = NULL;
    tr->capecity = tr->size = 0;
}

void rea_cp(SL* tr)//扩容
{
    int new_capecity = tr->capecity == 0 ? 4 : tr->capecity * 2;
    int* tep = (int*)realloc(tr->vate, sizeof(int)*new_capecity);
    tr->vate = tep;
    tr->capecity = new_capecity;
}

int* reOrderArray(int* array, int arrayLen, int* returnSize ) 
{
    // write code here
    SL tr_1, tr_2;//声明两个结构体对象
    init(&tr_1);//初始化两个结构体
    init(&tr_2);
    for(int i = 0; i<arrayLen; i++)//区分
    {
        if(array[i] % 2 == 0)//偶数放在tr_2中
        {
            if(tr_2.size == tr_2.capecity)//检查空间
            {
                rea_cp(&tr_2);
            }
            tr_2.vate[tr_2.size++] = array[i];
        }
        else//奇数放在tr_1中
        {
            if(tr_1.size == tr_1.capecity)//检查空间
            {
                rea_cp(&tr_1);
            }
            tr_1.vate[tr_1.size++] = array[i];
        }
    }
    if(tr_2.size == arrayLen)//若偶数组等于原数组数位，则代表全是偶数，返回
    {
        *returnSize = tr_2.size;
        return tr_2.vate;
    }
    if(tr_1.size == arrayLen)//若基数组等于原数组数位，则代表全是奇数，返回
    {
        *returnSize = tr_1.size;
        return tr_1.vate;
    }
    for(int j = 0; j < tr_2.size; j++)//如果不是以上，则将偶数组元素插入倒奇数组后
    {
        if(tr_1.size == tr_1.capecity)//检查扩容
        {
            rea_cp(&tr_1);   
        }
        tr_1.vate[tr_1.size++] = tr_2.vate[j];//倒数
    }
    *returnSize = tr_1.size;//返回
    return tr_1.vate;
}

发表于 2022-08-14 23:05:11 回复(0)

小羊咖啡

请问为什么*returnSize=arrayLen; 结果就是对的。而*returnSize=sizeof(arr)/sizeof(arr[0]);结果不正确呢？

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    //*returnSize=数组元素个数
    int* arr=(int*)calloc(arrayLen, sizeof(int));
    //int* arr=(int*)malloc(sizeof(int)*arrayLen);
    //memset(arr,0,sizeof(int)*arrayLen);
    int j=0;
    for(int i=0;i<arrayLen;i++)
    {
        if(array[i]%2!=0)
        {
            arr[j++]=array[i];
        }
    }
    for(int k=0;k<arrayLen;k++)
    {
        if(array[k]%2==0)
        {
            arr[j++]=array[k];
        }
    }
    //*returnSize=sizeof(arr)/sizeof(arr[0]); //错误
    *returnSize=arrayLen;
    return arr;
    free(arr);
}

发表于 2022-05-24 18:13:33 回复(0)

✨LAUGH

暴力一点，先按相对位置不变放奇数，再放偶数

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int j=0;
    * returnSize=arrayLen;
    int* s=(int*)malloc(sizeof(int)*arrayLen);
    for(int i=0;i<arrayLen;i++){
        if(array[i]%2==1){
            s[j]=array[i];
            j++;
        }     
    }
    for(int i=0;i<arrayLen;i++){
        if(array[i]%2==0){
            s[j]=array[i];
            j++;
        }
    }
    return s;
}

发表于 2022-05-06 16:34:12 回复(0)

赶紧离职

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
// write code here
int i=0,j=0;
int *a=(int *)malloc(sizeof(int)*arrayLen);
* returnSize=arrayLen;
for(i=0;i<arrayLen;i++){
if(array[i]%2!=0){a[j++]=array[i];}//奇数
}
for(i=0;i<arrayLen;i++){
if(array[i]%2==0){a[j++]=array[i];}//偶数
}
return a;
}

发表于 2021-11-15 23:43:49 回复(0)

小酷爱

创建一个数组来存储新的奇偶数，设定两个变量left、right来判断原数组是否奇偶数，具体看代码

C代码如下：

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    int array2[5000] = {0};
    int left = 0, right = arrayLen-1;
    int i = 0, j = arrayLen-1;
    while(left < arrayLen)
    {
        if(array[left] % 2 == 1)
            array2[i++] = array[left];
        //第一个元素要是奇数就放到新数组里的0下标
        if(array[right] % 2 == 0)
            array2[j--] = array[right];
        //最后一个元素是偶就放到新数组的尾下标
        left++,right--;
        //不管上面判断是否进，left、right往自己的方向走
    }
    *returnSize = left;//最终left走到的位置就是数组的长度
    return array2;
}

发表于 2021-11-08 16:59:41 回复(0)

海饼干666

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    *returnSize = 0;
    if(arrayLen == 0) return NULL;
    int *Retarray = (int*)malloc(arrayLen*sizeof(int));
    memset(Retarray, 0, arrayLen);
    
    for(int i = 0; i < arrayLen; i++)
    {
        if(array[i] % 2 == 1) 
        {
            Retarray[*returnSize] = array[i];
            *returnSize = *returnSize + 1;
        }
    }
    
    for(int i = 0; i < arrayLen; i++)
    {
        if(array[i] % 2 == 0) 
        {
            Retarray[*returnSize] = array[i];
            *returnSize = *returnSize + 1;
        }
    }
    return Retarray;
}

发表于 2021-08-30 17:18:59 回复(0)

勇敢牛牛，不怕困难！

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
  int* ans = (int*) malloc(arrayLen * sizeof(int));
  *returnSize = 0;
  if (!ans) return NULL;
  
  int i;
  for (i = 0; i < arrayLen; ++i)
    if (array[i] & 1) *(ans + (*returnSize)++) = array[i];
  
  for (i = 0; i < arrayLen; ++i)
    if (array[i] % 2 == 0) *(ans + (*returnSize)++) = array[i];
  
  return ans;
}

发表于 2021-07-27 08:56:16 回复(0)

提交观点

问题信息

数组

上传者：牛客301499号

难度：

10条回答 455收藏 6940浏览

通过挑战的用户

查看代码

求求上天给我o...

2022-09-20 09:53:59
牛客31742...

2022-09-19 09:11:38
Levi丶acm

2022-09-16 17:47:34
牛客66488...

2022-09-16 10:51:42
优秀的羚羊爱健身

2022-09-16 09:36:31

调整数组顺序使奇数位于偶数前面(一)

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题