【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

本问题对应课程链接：剑指offer刷题第五期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 69 6

共以下 6 个回答

sc_Yang 普通 2023年9月15日上午7:56

利用vector的删除元素，然后再在末尾新增元素的方式进行分奇偶类

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        vector<int>::iterator iter = nums.begin();
        for(int i = 0; i<nums.size(); i++){
            if((*iter)%2 == 0){
                auto tmp = *iter;
                iter = nums.erase(iter);
                nums.push_back(tmp);
            }else{
                iter = iter+1;
            }
        }
        return nums;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月8日上午11:22

class Solution {
    public int[] exchange(int[] nums) {
        //时间复杂度为O(N)，空间复杂度为O(1)
        int left = 0, right = nums.length - 1;
        while (left < right) {
            //找到左侧第一个非奇数
            while (left < right && nums[left] % 2 == 1) {
                left ++;
            }
            //找到右侧第一个非偶数
            while (left < right && nums[right] % 2 == 0) {
                right --;
            }
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left ++;
                right --;
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月6日上午10:16

思路：双指针i、j分别从两边用于找偶数和奇数，找到后交换
复杂度：时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            while ((i < j) && (nums[i] & 1) == 1) {
                i++;
            }
            while ((i < j) && (nums[j] & 1) == 0) {
                j--;
            }
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月6日上午1:51

双指针

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            while(left < right && nums[right]%2 == 0){
                right--;
            }
            while(left < right && nums[left]%2 == 1){
                left++;
            }
            int tmp = nums[right];
            nums[right] = nums[left];
            nums[left] = tmp;
        }
        return nums;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月5日下午10:09

//时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int i=0;
        int j=nums.size()-1;
        while(i<j)
        {
            if(nums[i]%2==0) swap(nums[i],nums[j--]);
            else 
            {
                i++;
            }
        }
        return nums;
    }
};

//快排思想
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int i=0;
        int j=nums.size()-1;
        while(i<j)
        {
            while(i<j && nums[i]%2==1) i++;
            while(i<j && nums[j]%2==0) j--;
            swap(nums[i],nums[j]);
        }
        return nums;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月5日下午7:31

快排，两个指针一个从前往后找偶数，一个从后往前找奇数。
时间复杂度O(n),空间复杂度O(1)

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            while (i < j && nums[j] % 2 == 0) {
                j--;
            }
            while (i < j && nums[i] % 2 == 1) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

共以下 6 个回答

# 回答此问题 取消回复

# 回答此问题取消回复