当前位置：
  1. 首页
  2. 剑指offer刷题第四期
  3. 问题详情

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

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

要求：

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

shuaidi
121 16

共以下 16 个回答

  • hi 普通 2023年9月14日 上午8:36
    1. 双指针算法，进入循环后，还需判断 l < r
    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        //快排：分治+双指针，此题只用到双指针
        int n = nums.size();
        int l = 0, r = n - 1;

        while(l < r) {
            while(l < r && nums[l] % 2 == 1) l++; 
            while(l < r && nums[r] % 2 == 0) r--;
            if(l < r) swap(nums[l], nums[r]);
        }
        return nums;
}    
};
    0 赞同 0 条回复
  • 桎梏 普通 2023年9月11日 上午10:19 
    //双指针
class Solution {
    public int[] exchange(int[] nums) {

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

        return nums;
    }
}
    0 赞同 0 条回复
  • June 普通 2023年9月10日 下午4:20 
    class Solution {
    public int[] exchange(int[] nums) {
        int L = 0,R = nums.length - 1;
        //双指针
        while(L <= R) 
        {
            if(nums[L]%2 == 0 && nums[R]%2 == 1) 
            {
                int tmp = nums[L]; nums[L] = nums[R];
                nums[R] = tmp;
                L++;
                R--;
            }
            else if(nums[L]%2 == 1 && nums[R]%2 == 1)
            {
                L++;
            }
            else if(nums[L]%2 == 0 && nums[R]%2 == 0)
            {
                R--;
            }
            else
            {
                L++;
                R--;
            }
        }
        return nums;
    }
}
    0 赞同 0 条回复
  •  普通 2023年8月10日 下午10:53

    c++ 代码 先分开 奇数偶数分别排序
    class Solution {
    public:
    vector exchange(vector& nums)
    {
    vector     q,o,cur;
    for(int i=0;i<nums.size();i++)
    {
    if(nums[i]%2)
    q.push_back(nums[i]);
    else
    o.push_back(nums[i]);
    }
    sort(q.begin(),q.end());
    sort(o.begin(),o.end());
    for(int i=0;i<q.size();i++)
    cur.push_back(q[i]);
    for(int i=0;i<o.size();i++)
    cur.push_back(o[i]);
    return cur;
    }
    };

    0 赞同 0 条回复
  • 北辰 普通 2023年8月8日 上午10:50 
    int n = nums.length;
        int[] res = new int[n];
        int k=0;
        for(int num:nums) {
            if(num%2==1) {
                res[k++]=num;
            }
        }
        for(int num:nums) {
            if(num%2==0) {
                res[k++]=num;
            }
        }
        return res;

    遍历两编

    0 赞同 0 条回复
  • CKX 普通 2023年8月7日 下午11:24 
    func exchange(nums []int) []int {
    fast, slow := 0, 0
    for fast < len(nums) {
        if nums[fast] % 2 == 1 {
            //fast指向奇数
            swap(&nums[fast], &nums[slow])
            slow++
        }
        fast++
    }
    return nums
}

func swap(a, b *int) {
    temp := *a
    *a = *b
    *b = temp
}
    • 时间O(n)
    • 空间O(1)
    0 赞同 0 条回复
  • 艺 普通 2023年8月5日 下午5:16

    “`c++
    //双指针
    class Solution {
    public:
    vector exchange(vector& nums) {
    vector     s=nums;
    if(nums.size()<=1) return s; int l=0,r=s.size()-1; while(l

    0 赞同 0 条回复
  • #00456B 普通 2023年8月4日 上午12:35 
    class Solution {
public:
    // vector<int> exchange(vector<int>& nums) {
    //     //二分法，空间O(n)
    //     int n = nums.size();
    //     int left = 0;
    //     int right = n - 1;
    //     vector<int> ans(n);
    //     for(int x:nums){
    //         if(x % 2 == 1){
    //             ans[left] = x;
    //             left++;
    //         }
    //         else{
    //             ans[right] = x;
    //             right--;
    //         }
    //     }
    //     return ans;
    // }
    // vector<int> exchange(vector<int>& nums) {
    //     //二分法，空间O(1)
    //     int slow = 0;
    //     int fast = 0;
    //     for(int x:nums){
    //         if(x % 2 == 1){//如果是奇数，交换nums[slow]和nums[fast]
    //             int temp = nums[fast];
    //             nums[fast] = nums[slow];
    //             nums[slow] = temp;
    //             slow++;
    //         }
    //         fast++;
    //     }
    //     return nums;
    // }
    vector<int> exchange(vector<int>& nums) {
        //快排
        int left = 0;
        int right = nums.size() - 1;
        while(left < right){
            while(left < right && nums[left]%2 == 1) left++;//左指针找到第一个偶数
            while(left < right && nums[right]%2 == 0) right--;//右指针找到第一个奇数
            swap(nums[left], nums[right]);
        }
        return nums;
    }
};
    0 赞同 0 条回复
  • NullPointerException 普通 2023年8月3日 下午6:50

    class Solution {
    public int[] exchange(int[] nums) {
    //双指针 从中间开始 感觉跟快排一样

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

    }

    0 赞同 0 条回复
  • Marshan 普通 2023年8月3日 下午2:48

    类似快速排序的思想

    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;

        while(left < right){
            while(nums[left]%2 == 1 && left < right){
                left++;
            }
            while(nums[right]%2 == 0 && left < right){
                right--;
            }
            swap(nums[left],nums[right]);

        }

        return nums;
    }
};
    0 赞同 0 条回复
  • Mby 普通 2023年8月2日 下午10:07 
    class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left < right && nums[left] % 2 != 0)left++;
            while(left < right && nums[right] % 2 != 1)right--;

            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
        //时间复杂度：O(n)
        //空间复杂度：O(1)
    }
}
    0 赞同 0 条回复
  • 人生何处不青山 普通 2023年8月1日 下午11:31

    快排思想

    function exchange(nums: number[]): number[] {
    let l = 0,r = nums.length - 1;
    while(l < r) {
        while(l < r && nums[l] % 2 === 1) {
            l++;
        }
        while(l < r && nums[r] %2 === 0) {
            r--;
        }
        [nums[l],nums[r]] = [nums[r],nums[l]]
    }
    return nums;
};
    0 赞同 0 条回复
  • AD钙奶 普通 2023年8月1日 上午10:40

    快排思想

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

            if(i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        } 
    }
}
    0 赞同 0 条回复
  • 长河呼叫黄江 普通 2023年7月31日 下午11:50

    7.31
    Day22：下面是代码

    class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while(i < j) {
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}
    0 赞同 0 条回复
  • 阿尚 普通 2023年7月31日 下午8:11 
    class Solution {
//双指针
    public int[] exchange(int[] nums) {

        int l = 0;
        int r = nums.length - 1;

        while(l < r){
            while(l < r && nums[l] % 2 != 0) l++;
            while(l < r &&nums[r] % 2 == 0) r--;
            if(l < r){
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }

        return nums;
    }
}

class Solution {
    public int[] exchange(int[] nums) {
        // 维护 nums[0..slow) 都是奇数
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] % 2 == 1) {
                // fast 遇到奇数，把 nums[fast] 换到 nums[slow]
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
        }
        return nums;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年7月31日 下午3:06 
    //空间复杂度比较高 比骄容易想到
public int[] exchange(int[] nums) {
            int[] res = new int[nums.length];
            List<Integer> odd = new ArrayList<>();
            List<Integer> even = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]%2 == 0) {
                    even.add(nums[i]);
                } else if (nums[i]%2 == 1) {
                    odd.add(nums[i]);
                }
            }
            for (int i = 0; i < odd.size(); i++) {
                res[i] = odd.get(i);
            }
            for (int i = 0; i < even.size(); i++) {
                res[i+odd.size()] = even.get(i);
            }
            return res;
        }
    0 赞同 0 条回复

# 回答此问题

后才能回答