【劍指Offer】調整數組順序使奇數位於偶數前面

題目描述

輸入一個整數數組,實現一個函數來調整該數組中数字的順序,使得所有的奇數位於數組的前半部分,所有的偶數位於數組的後半部分,並保證奇數和奇數,偶數和偶數之間的相對位置不變。

解法1

最直接的思路是再構建一個新數組,先遍歷一遍原數組,把其中的奇數依次添加到新數組中,再遍歷一遍原數組把其中的偶數依次添加到新數組中,時間複雜度為O(2n)。實現代碼如下

實現代碼

public int[] reOrderArray2(int[] array)
{
    int[] arr = new int[array.Length];
    int index = 0;
    for (int i = 0; i < array.Length; i++)
    {
        // 奇數
        if ((array[i] % 2) != 0)
        {
            arr[index] = array[i];
            index++;
        }
    }
    for (int i = 0; i < array.Length; i++)
    {
        // 偶數
        if ((array[i] % 2) == 0)
        {
            arr[index] = array[i];
            index++;
        }
    }
    return arr;
}

解法2

C#的數組是不支持動態添加元素的,我們可以使用泛型List,來實現在指定位置插入元素。基本思路是遍歷原數組,依次將元素插入到List中,如果是偶數元素,默認插入到List的末尾。如果是奇數元素,則插入到所有的偶數元素之前(已插入的所有奇數元素之後),因此需要記錄最後插入的奇數元素的索引。實現代碼如下,算法的時間複雜度是O(n)

實現代碼

public int[] reOrderArray(int[] array)
{
    List<int> list = new List<int>();
    // 最後插入奇數元素的索引
    int index = 0;
    foreach (int i in array)
    {
        if ((i % 2) == 0)
            list.Add(i);
        else
        {
            list.Insert(index, i);
            index++;
        }
    }
    return list.ToArray();
}

解法3

上面的兩種解法都用到臨時數組或List,空間複雜度是O(n),某些情況下可能希望空間複雜度越低越好。下面這種解法雖然時間複雜度提高了,但降低了空間複雜度,不再需要額外的空間。基本思路是遍歷原數組,如果遇到了奇數元素,就將該元素向前移動,該元素前面的偶數元素都依次向後移動。
舉個例子:比如數組{1, 2, 4, 3, 5}
遍曆數組,得到第一個元素是奇數1,其前面沒有元素所以不做移動
第二個,第三個是偶數,不做處理。
第四個元素是奇數3,所以將3往前移動,3前面的偶數元素{2, 4}都向後移動。移動后的數組為{1, 3, 2, 4, 5}
接着第五個元素是奇數5,所以將5往前移動,5前面的偶數元素{2, 4}都向後移動。移動后的數組為{1, 3, 5, 2, 4}
可以這樣理解,每發現一個奇數時,就將這個奇數移動到了它最終應該在的位置上。

實現代碼

public int[] reOrderArray(int[] array)
{
    for(int i = 0; i < array.Length; i++)
    {
        if((array[i] % 2) != 0)
        {
            int temp = array[i];
            int j = i - 1;
            for(; j >= 0; j--)
            {
                if ((array[j] % 2) != 0)
                    break;
                array[j + 1] = array[j]; 
            }
            array[j + 1] = temp;
        }
    }
    return array;
}

【精選推薦文章】

自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

您可能也會喜歡…