題目：輸入一個整數(shù)數(shù)組，實(shí)現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序腹备，使得所有的奇數(shù)位于數(shù)組的前半部分傻工，所有的偶數(shù)位于數(shù)組的后半部分。
練習(xí)地址
劍指 Offer 21. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面 - 力扣（LeetCode） (leetcode-cn.com)
參考答案
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int begin = 0, end = array.length - 1;
while (begin < end) {
// 向后移動begin专控，直到它指向偶數(shù)
while (begin < end && (array[begin] & 1) > 0) {
begin++;
}
// 向前移動end，直到它指向奇數(shù)
while (begin < end && (array[end] & 1) == 0) {
end--;
}
if (begin < end) {
int temp = array[begin];
array[begin] = array[end];
array[end] = temp;
}
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)遏餐。
- 空間復(fù)雜度：O(1)伦腐。
擴(kuò)展：輸入一個整數(shù)數(shù)組，實(shí)現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序失都，使得所有的奇數(shù)位于數(shù)組的前半部分柏蘑，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)粹庞，偶數(shù)和偶數(shù)之間的相對位置不變咳焚。
練習(xí)地址
https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593
參考答案
public class Solution {
public void reOrderArray(int [] array) {
int n = array.length;
int[] aux = new int[n];
int i = 0;
for (int j = 0; j < n; j++) {
if ((array[j] & 1) == 1) {
if (i != j) {
array[i] = array[j];
}
i++;
} else {
aux[j - i] = array[j];
}
}
for (int j = i; j < n; j++) {
array[j] = aux[j - i];
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)。
- 空間復(fù)雜度：O(n)信粮。
