目录
一、题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
示例:
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
提示:
0 <= nums.length <= 50000
0 <= nums[i] <= 10000
二、思路讲解
借用快速排序的思想,用两个指针分别从头尾出发,左指针如果碰见奇数就继续往右,右指针如果碰见偶数就一直往左。当左指针碰到偶数、右指针碰到奇数时,交换两个指针的数,继续往中间寻找,知道两指针交汇。
三、Java代码实现
class Solution {
public int[] exchange(int[] nums) {
int i=0;
int j=nums.length-1;
while(i < j){
//左指针找偶数,找到就跳出
while(i<j && nums[i]%2!=0){
i++;
}
//右指针找奇数,找到就跳出
while(i<j && nums[j]%2==0){
j--;
}
//交换两个指针的数
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
return nums;
}
}
四、时空复杂度分析
时间复杂度 O(N)
空间复杂度 O(1)
五、另一种双指针(效率较低)
class Solution {
public int[] exchange(int[] nums) {
int len = nums.length;
if (len==0 || len==1){
return nums;
}
int i = 0;
int j = 1;
while(i<len && j<len) {
if(nums[i]%2 != 0){ //左指针为奇数
i++;
j++;
} else { //左指针为偶数
if(nums[j]%2 != 0) { //左指针为偶数,右指针为奇数
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j = i+1;
} else { //左指针为偶数,右指针为偶数
j++;
}
}
}
return nums;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/125061.html