腾讯云服务器怎么搭建网站,成都最差的十大物业公司,哪个网站能查是否做股东,比购网❓剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
难度#xff1a;简单
输入一个整数数组#xff0c;实现一个函数来调整该数组中数字的顺序#xff0c;使得所有奇数在数组的前半部分#xff0c;所有偶数在数组的后半部分。
示例#xff1a; 输入#xff1a;nums [1…❓剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
难度简单
输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有奇数在数组的前半部分所有偶数在数组的后半部分。
示例 输入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 0nums.length50000 0 n u m s [ i ] 10000 0 nums[i] 10000 0nums[i]10000
思路双指针
先从 nums 左侧开始遍历如果遇到的是奇数就表示这个元素已经调整完成了继续从左往右遍历直到遇到一个偶数。然后从 nums右侧开始遍历如果遇到的是偶数就表示这个元素已经调整完成了继续从右往左遍历直到遇到一个奇数。交换这个偶数和奇数的位置并且重复两边的遍历直到在中间相遇nums 调整完成。
代码(C、Java)
C
class Solution {
public:vectorint exchange(vectorint nums) {int l 0, r nums.size() - 1;while(l r){//从前往后找到第一个偶数while(l r nums[l] % 2 ! 0) l;//从后往前找到第一个奇数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){//从前往后找到第一个偶数while(l r nums[l] % 2 ! 0) l;//从后往前找到第一个奇数while(l r nums[r] % 2 0) r--;//交换int temp nums[l];nums[l] nums[r];nums[r--] temp;}return nums;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)原数组中每个元素只遍历一次。空间复杂度 O ( 1 ) O(1) O(1)原地调整只消耗常数空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
