(绝密算法数组奇偶排序)——游戏里iu后面所有的符号谁会打

版权声明:本文为博主原创文章遵循<a href="

给定一个非负整数数组 A, A 中一半整数是奇数一半整数是偶数。?

对数组进行排序以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时 i 也昰偶数。

你可以返回任何满足上述条件的数组作为答案

遍历一遍数组把所有的偶数放进 ans[0],ans[2]ans[4],依次类推

再遍历一遍数组把所有的奇数依次放进 ans[1],ans[3]ans[5],依次类推

时间复杂度:O(N),其中 N 是数组 A 的长度

空间复杂度:O(1)。注意在这里我们不考虑输出数组的空间占用

如果原数组鈳以修改,则可以使用就地算法求解

为数组的偶数下标部分和奇数下标部分分别维护指针 i,j随后,在每一步中如果 A[i] 为奇数,则不断哋向前移动 j(每次移动两个单位)直到遇见下一个偶数。此时可以直接将 A[i] 与 A[j] 交换。我们不断进行这样的过程最终能够将所有的整数放在正确的位置上。

时间复杂度:O(N)其中 N 是数组 A 的长度。

空间复杂度:O(1)

声明:本文归“力扣”版权所有,如需转载请联系

我要回帖

更多关于 数组奇偶排序 的文章

 

随机推荐