版权声明:本文为博主原创文章遵循<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)
声明:本文归“力扣”版权所有,如需转载请联系