将前半部分的所有偶数移动到整数数组中的后半部分

Question

我有一个面试问题,我无法解决.

Java编程语言中的写方法(不是程序),它将在前半部分中将所有偶数移动到整数数组中的后半部分.

例如输入= {3,8,12,5,9,21,6,10}; 输出= {12,8,6,10,3,5,9,21}.

该方法应将整数数组作为参数并在同一数组中移动项目(不要创建另一个数组).数字可能与原始数组的顺序不同.这是算法测试,因此尽量提供尽可能高效的算法(可能是线性O(n)算法).避免使用内置函数/ API.*

还有一些基本介绍什么是数据结构效率

Answer 1

保留两个索引:一个到第一个奇数,一个到最后一个偶数.交换这些数字并更新索引.

Answer 2

(在@ manu-fatto建议的帮助下)我相信这样做会:

private static int[] OddSort(int[] items)
{
    int oddPos, nextEvenPos;
    for (nextEvenPos = 0; 
         nextEvenPos < items.Length && items[nextEvenPos] % 2 == 0;
         nextEvenPos++) { }
    // nextEvenPos is now positioned at the first odd number in the array, 
    // i.e. it is the next place an even number will be placed

    // We already know that items[nextEvenPos] is odd (from the condition of the 
    // first loop), so we'll start looking for even numbers at nextEvenPos + 1
    for (oddPos = nextEvenPos + 1; oddPos < items.Length; oddPos++)
    {
        // If we find an even number
        if (items[oddPos] % 2 == 0)
        {
            // Swap the values
            int temp = items[nextEvenPos];
            items[nextEvenPos] = items[oddPos];
            items[oddPos] = temp;
            // And increment the location for the next even number
            nextEvenPos++;
        }
    }

    return items;
}

该算法精确遍历列表一次(每个元素只检查一次),因此效率为O(n).