【劍指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;
}
【精選推薦文章】
自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象
網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!
評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"