题目:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
示例:
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
提示:
0 <= nums.length <= 50000
0 <= nums[i] <= 10000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
方法一:另创建数组
1 class Solution { 2 public int[] exchange(int[] nums) { 3 if (nums.length == 0 || nums == null) return new int[0]; 4 int[] ans = new int[nums.length]; 5 int n = 0, m = nums.length - 1; 6 while(n <= m){ 7 for (int i = 0; i < nums.length; i++){ 8 if (nums[i] % 2 == 0){ 9 ans[m] = nums[i]; 10 m--; 11 }else{ 12 ans[n] = nums[i]; 13 n++; 14 } 15 } 16 } 17 return ans; 18 } 19 }
方法二:双指针,利用位运算进行优化
1 class Solution { 2 public int[] exchange(int[] nums) { 3 if (nums.length == 0) return new int[0]; 4 int n = nums.length; 5 int i = 0, j = n - 1; 6 while(i <= j){ 7 if ((nums[i] & 1) == 1){ 8 i++; 9 }else if ((nums[j] & 1) == 0){ 10 j--; 11 }else if ((nums[i] & 1) == 0 && (nums[j] & 1) == 1){ 12 int temp = nums[i]; 13 nums[i] = nums[j]; 14 nums[j] = temp; 15 } 16 } 17 return nums; 18 } 19 }
或者
1 class Solution { 2 public int[] exchange(int[] nums) { 3 if (nums.length == 0) return new int[0]; 4 int n = nums.length; 5 int i = 0, j = n - 1; 6 while(i < j){ 7 while (i < j && (nums[i] & 1) == 1) i++; 8 while (i < j && (nums[j] & 1) == 0) j--; 9 if ((nums[i] & 1) == 0 && (nums[j] & 1) == 1){ 10 int temp = nums[i]; 11 nums[i] = nums[j]; 12 nums[j] = temp; 13 } 14 } 15 return nums; 16 } 17 }
注意:内部while循环也要判断一下的理由:当数组全部为奇数[1,3,5,7]或全部为偶数[2,4,6,8]时,当走到最边上的数后就会越界。
小知识:
判断奇偶性:用位运算代替 (% 2)
(nums[i]&1)==1 奇数判断,原理:奇数的最低位为1
(nums[i]&1)==0 偶数判断,原理:偶数的最低位为0
&运算规则: 0&0=0;0&1=0;1&0=0;1&1=1 即:两个同时为1,结果为1。
注意:位运算的优先级比较低,不要吝啬括号的使用。