【劍指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;
 }

【精選推薦文章】

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

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

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

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

---

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