?劍指 Offer 21. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
難度：簡單
輸入一個整數(shù)數(shù)組，實(shí)現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)在數(shù)組的前半部分，所有偶數(shù)在數(shù)組的后半部分。
示例：
輸入：nums = [1,2,3,4]
輸出：[1,3,2,4]
注：[3,1,2,4] 也是正確的答案之一。
提示：
- 0 < = n u m s . l e n g t h < = 50000 0 <= nums.length <= 50000 0<=nums.length<=50000
- 0 < = n u m s [ i ] < = 10000 0 <= nums[i] <= 10000 0<=nums[i]<=10000
??思路：雙指針
- 先從
nums左側(cè)開始遍歷，如果遇到的是奇數(shù)，就表示這個元素已經(jīng)調(diào)整完成了，繼續(xù)從左往右遍歷，直到遇到一個偶數(shù)。 - 然后從
nums右側(cè)開始遍歷，如果遇到的是偶數(shù)，就表示這個元素已經(jīng)調(diào)整完成了，繼續(xù)從右往左遍歷，直到遇到一個奇數(shù)。 - 交換這個偶數(shù)和奇數(shù)的位置，并且重復(fù)兩邊的遍歷，直到在中間相遇，
nums調(diào)整完成。
??代碼：(C++、Java)
C++
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while(l < r){
//從前往后找到第一個偶數(shù)
while(l < r && nums[l] % 2 != 0) l++;
//從后往前找到第一個奇數(shù)
while(l < r && nums[r] % 2 == 0) r--;
//交換
swap(nums[l++], nums[r--]);
}
return nums;
}
};
Java
class Solution {
public int[] exchange(int[] nums) {
int l = 0, r = nums.length - 1;
while(l < r){
//從前往后找到第一個偶數(shù)
while(l < r && nums[l] % 2 != 0) l++;
//從后往前找到第一個奇數(shù)
while(l < r && nums[r] % 2 == 0) r--;
//交換
int temp = nums[l];
nums[l++] = nums[r];
nums[r--] = temp;
}
return nums;
}
}
?? 運(yùn)行結(jié)果：
?? 復(fù)雜度分析：
- 時間復(fù)雜度： O ( n ) O(n) O(n)，原數(shù)組中每個元素只遍歷一次。
- 空間復(fù)雜度： O ( 1 ) O(1) O(1)，原地調(diào)整，只消耗常數(shù)空間。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-661059.html
放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-661059.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(排序) 劍指 Offer 21. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
