|
The human voice can never reach the distance that is covered by the still small voice of conscience.
良心之聲寂靜微小,，但它傳遞的距離是人聲永遠達不到的,。 問題描述給一個整數(shù)數(shù)組,，讓它的奇數(shù)和偶數(shù)分開并且奇數(shù)在數(shù)組的前面，偶數(shù)在數(shù)組的后面,。
問題分析這題沒什么難度,，首先最容易想到的是申請一個同樣大小的臨時數(shù)組，把原數(shù)組的值放到臨時數(shù)組中,，奇數(shù)從前面放,，偶數(shù)從后面放，我們來看下代碼
1public int[] exchange(int[] nums) {
2 if (nums == null || nums.length == 0)
3 return nums;
4 int left = 0;
5 int right = nums.length - 1;
6 int temp[] = new int[nums.length];
7 for (int i = 0; i < nums.length; i++) {
8 if ((nums[i] & 1) == 0) {
9 //偶數(shù)從后面放
10 temp[right--] = nums[i];
11 } else {
12 //奇數(shù)從前面放
13 temp[left++] = nums[i];
14 }
15 }
16 return temp;
17}
我們可以使用兩個指針left和right,。left從左邊開始掃描,，如果是奇數(shù)就往右走，如果遇到偶數(shù)就停下來（此時left指向的是偶數(shù)）,，right從右邊開始掃描，如果是偶數(shù)就往左走,，如果是奇數(shù)就停下來（此時right指向的是奇數(shù)）,，交換left和right指向的值。繼續(xù)循環(huán),，直到left==right為止,。我們就以數(shù)組[3，2,，4,，9，5,，8,，1]為例來畫個圖看一下
1public static int[] exchange(int[] nums) {
2 if (nums == null || nums.length == 0)
3 return nums;
4 int left = 0;
5 int right = nums.length - 1;
6 while (left < right) {
7 //如果是奇數(shù)，就往后挪,，直到遇到偶數(shù)為止
8 while (left < right && (nums[left] & 1) == 1) {
9 left++;
10 }
11 //如果是偶數(shù),，就往前挪，直到遇到奇數(shù)為止
12 while (left < right && (nums[right] & 1) == 0) {
13 right--;
14 }
15 //交換兩個值
16 if (left < right) {
17 nums[left] ^= nums[right];
18 nums[right] ^= nums[left];
19 nums[left] ^= nums[right];
20 }
21 }
22 return nums;
23}
代碼16到20行是交換兩個數(shù)字的值,，交換兩個數(shù)的值有多種方式,，這里選擇的是通過異或來交換，如果看不明白可以看一下下面往期推薦中的第357題,。
第三種方式使用的是快慢指針,，和上一種解決方式有一點區(qū)別,，上一種是一前一后掃描。我們這里使用的快慢指針都是從頭開始掃描,。我們使用兩個指針,，一個快指針fast，一個慢指針slow,。慢指針slow存放下一個奇數(shù)應該存放的位置,，快指針fast往前搜索奇數(shù)，搜索到之后然后就和slow指向的值交換,，我們還以上面的數(shù)據(jù)為例畫個圖來分析下
1public static int[] exchange(int[] nums) {
2 int slow = 0, fast = 0;
3 while (fast < nums.length) {
4 if ((nums[fast] & 1) == 1) {//奇數(shù)
5 if (slow != fast) {
6 nums[slow] ^= nums[fast];
7 nums[fast] ^= nums[slow];
8 nums[slow] ^= nums[fast];
9 }
10 slow++;
11 }
12 fast++;
13 }
14 return nums;
15}
|
