关于c++:leetcodeJZ21

55次阅读

共计 921 个字符,预计需要花费 3 分钟才能阅读完成。

题面

输出一个整数数组,实现一个函数来调整该数组中数字的程序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半局部。

示例:

输出:nums = [1,2,3,4]
输入:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

提醒:

0 <= nums.length <= 50000
1 <= nums[i] <= 10000

原题链接

剖析

刚开始想到思路 1:

从前向后遍历数组,遇到奇数时,什么也不做;遇到偶数时,把该偶数删除,而后把该偶数放到数组前面

然而这种思路会 超时

上面剖析超时起因:

数组最大长度为 50000,思路 1 绝不仅仅是简略的遍历数组,工夫复杂度为 O(N),思路 1 还波及到数组的插入、删除,删除操作(erase)的复杂度就是 O(N),最坏状况下,工夫复杂度为 O(N2),太大。

接下来想到思路 2:

采纳双指针,left 指向数组首部,right 指向数组尾部,left 总体趋势向右挪动,right 总体趋势向左挪动

上面剖析这种思路不超时的起因:

只遍历数组一遍,工夫复杂度为 O(N)。

源代码(正文局部即为思路)

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {int len =  nums.size();
        int left = 0;
        int right = len-1;
        while(left<right){
            // 左偶、右奇
            if(nums[left]%2==0 && nums[right]%2==1){// 替换数组元素的操作其实很简略,工夫复杂度 O(1),空间复杂度 O(1)
                int tmpL = nums[left];
                int tmpR = nums[right];
                nums[left] = tmpR;
                nums[right] = tmpL;
                left++;
                right--;
            }
            // 左偶、右偶
            if(nums[left]%2==0 && nums[right]%2==0){right--;}
            // 左奇、右偶
            if(nums[left]%2==1 && nums[right]%2==0){
                left++;
                right--;
            }
            // 左奇、右奇
            if(nums[left]%2==1 && nums[right]%2==1){left++;}

        } 
        return nums;
    }
};

提交后果:

正文完
 0