首先 - 这不是作业 - 我在上次采访中得到了这个问题而无法完成 .
所以问题是这样的:“给定长度为n的int数组k,'删除'所有偶数并将奇数移到前面” . 它的措辞有点奇怪,因为他们说删除,但实例表明我应该把所有奇数放在数组前面(从0索引开始),偶数数字可以保留在数组中(或者不是 - 它没关系)经过所有奇数 . 例:
{1, 4, 6, 8, 7, 2} -> {1, 7, whatever}
{2, 4, 6, 9, 5} -> {9, 5, whatever}
我希望尽可能高效 . 我无法使用任何其他库或临时数组 .
到目前为止得到了这个但是被卡住了
private static void removeEven(int[] k, int n) {
for (int i = 0; i < n; i++) {
if (k[i] % 2 == 0) {
k[i] = // don't know
}
}
7 回答
我想你需要在循环内部有一个计数器来记忆返回数组的位置 . 我已经使用了这个代码,将所有剩余的数组位置都设置为0 .
我希望这能回应你的回答!
我会颠倒这个方法,我的意思是代替删除偶数我会把奇数移到前面这是他们和他们不关心数组中剩下什么,所以我的方法就像
我想我只会维护指向数组中位置的两个变量 . 一个人会指向下一个偶数(从头开始),一个指向下一个奇数(从结尾开始) . 虽然下一个偶数的索引低于下一个奇数,但交换它们 . 这是工作和测试的代码:
这是O(n),这是我认为你可以在这里获得的最佳表现 .
这也比这里的许多其他答案表现更好,因为数字永远不会交换两次;也就是说,大多数其他解决方案遍历整个数组(有时会进行不必要的交换),而这只会迭代一半 .
这是解决方案:
如下所示的类似下面的伪代码将首先返回带有赔率的数组,最后一次,并将保留奇数和偶数子集的原始顺序 .
您可以使用临时变量放置要移动的值,而不是使用另一个变量来设置要移动值的位置 .
代码:
使用下面的代码,我们可以从数组中删除所有偶数并写入其余的数组 .