【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年6月6日下午11:14

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int temp = 0;
        while(left < right){
            if(nums[left] % 2 == 1){
                // 遇到奇数移动到下一位
                left ++;
            }else{
                // 遇到偶数进行交换，进入下一位
                temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                right --;
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

cute. 普通 2023年4月23日下午11:46

思路：使用位运算符和双指针结合

var exchange = function(nums) {
  let i = 0, j = nums.length - 1
  while (true) {
      while ((nums[i] & 1) && i < nums.length) {
          i++
      }
      while (!(nums[j] & 1) && j >= 0) {
          j--
      }
      if (i >= j) {
          break
      }
      [nums[i], nums[j]] = [nums[j], nums[i]]
  }
  return nums
};

0 赞同 0 条回复

宁永久会员 2023年3月15日上午11:33

移动指针的过程中要判断指针的位置

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

0 赞同 0 条回复

xye 普通 2023年2月24日上午11:05

func exchange(nums []int) []int {
    i, j := 0, len(nums) - 1
    for i < j {
        for i < j && nums[i] & 1 == 1 {
            i++
        }
        for i < j && nums[j] & 1 == 0 {
            j--
        }
        tmp := nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }
    return nums
}

时间O（n）空间O（1）

0 赞同 0 条回复

lucca 普通 2023年1月15日下午10:34

双指针

时间复杂度 O(N)
空间复杂度 O(1)

class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            while (l < r && (nums[l] & 1) == 1) l++;
            while (l < r && (nums[r] & 1) == 0) r--;
            if (l < r) {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月13日下午3:11

# 使用快排的思想，时间复杂度是o(n),空间复杂度是o（1）（不稳定）
def exchange(nums):
    if len(nums) == 1:
        return nums
    i = 0
    j = len(nums)-1

    while i < j:
        while i < j and nums[i] & 1 == 1:
            i += 1
        while i < j and nums[j] & 1 != 1:
            j -= 1
        if not i == j:
            # 此时i指向左边的偶数，j指向的右边奇数
            nums[i] = nums[i] ^ nums[j]
            nums[j] = nums[i] ^ nums[j]
            nums[i] = nums[i] ^ nums[j]

    return nums

0 赞同 0 条回复

庄重普通 2023年1月8日下午4:03

// 思路：
//     1.使用快速排序的思想，进行把奇偶顺序交换
//     2.只需要记住一个就行，写法1
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        if(nums.size() == 0) return nums;

        int l = 0, r = nums.size() - 1;

        while(l < r){
            //写法1：
            while (l < r && (nums[l] & 1) == 1) l++;
            while (l < r && (nums[r] & 1) == 0) r--;

            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;

            //最后的时候会有两个指针都指向同一个位置的情况，不要使用位运算进行交换顺序
            // if(l == r) break;
            // nums[l] = nums[l] ^ nums[r];
            // nums[r] = nums[l] ^ nums[r];
            // nums[l] = nums[l] ^ nums[r];


            //写法2：这样就避免了，最后一次两个指针都指向同一个位置的情况，使用位交换会出现0
            // if(l < r && (nums[l] & 1) == 1) l++;
            // else if(l < r && (nums[r] & 1) == 0) r--;
            // else{
            //     nums[l] = nums[l] ^ nums[r];
            //     nums[r] = nums[l] ^ nums[r];
            //     nums[l] = nums[l] ^ nums[r];
            // }
        }
    return nums;
    }
};
// 时间复杂度O(n)
// 空间复杂度O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年12月7日下午10:19

时间：O（n）
空间：O（1）

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        # 双指针，L指向偶数，R指向奇数时交换
        if not nums:
            return nums
        L, R = 0, len(nums) - 1
        while L <= R:
            if nums[L] % 2 == 0 and nums[R] % 2 == 1:
                temp = nums[L]
                nums[L] = nums[R]
                nums[R] = temp
            elif nums[L] % 2 != 0:
                L += 1
            elif nums[R] % 2 != 1:
                R -= 1
        return nums

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:35

func exchange(nums []int) []int {
      i,j:=0,len(nums)-1
      for i<j {       //循环条件
          if nums[i]%2==0 && nums[j]%2!=0{   //满足则发生交换
              nums[i],nums[j]=nums[j],nums[i]
          }
          if nums[i]%2!=0{     //i往后走
              i++
          }
          if nums[j]%2==0{     //j往前走
              j--
          }
      }
      return nums
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:30

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        vector<int> res;
        //1、双指针
        int i = 0;
        for(int j=1;j<nums.size();){ //np
            //奇数：对2取余为1，偶数：对2取余为0
            if(nums[i]%2==0 && nums[j]%2==1) {
                // swap(nums[i],nums[j]);
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp; 
                i++;
                j++;
            }
            else if(nums[i]%2==1 && nums[j]%2==0){
                i++;
                j++;
            }else if(nums[i]%2==1 && nums[j]%2==1){
                j++;
                i++;
            }else if(nums[i]%2==0 && nums[j]%2==0){
                j++;
            }
        }
        return nums;
    }
};

0 赞同 0 条回复

波波_1936 普通 2022年11月24日下午7:10

    public int[] exchange(int[] nums) {
        //时间复杂度O(n)
        //空间复杂度O(1)
        //双指针原地交换
        int left =0;
        int right = nums.length-1;
        while (left<right){
            while (left<=right&&(nums[left] & 1)==1){
                //奇数
                left++;
            }
            while (left<=right&&(nums[right] & 1)!=1){
                //偶数
                right--;
            }
            if(right<0||left>right){
                return nums;
            }
            //交换
            nums[left]=nums[left]^nums[right];
            nums[right]=nums[left]^nums[right];
            nums[left]=nums[left]^nums[right];
            left++;
            right--;
        }
        return nums;
    }

0 赞同 0 条回复

是梦终空永久会员 2022年11月23日下午11:32

时间O(n)
空间O(1)

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length == 0)    return nums;
        //双指针

        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left<right && nums[left] % 2 != 0){   //如果nums[left]为偶数，就把left指针左移
                left++;
            }    
            while(left < right && nums[right] % 2 != 1){    //如果nums[right]为奇数，就把right指针右移
                right--;
            }
            int temp = nums[left];                      //交换左右数
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月22日上午10:17

思路:双指针

时间复杂度O(N)
空间复杂度 O(1)

class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;

        while(true) {
            while(l <= r && nums[l] % 2 != 0)
                l++;

            while(r >= l && nums[r] % 2 == 0)
                r--;

            if(l >= r)
                break;

            swap(nums, l, r);

            l++;
            r--;

        }


        return nums;

    }

    private void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {2,16,3,5,13,1,16,1,12,18,11,8,11,11,5,1};
        s.exchange(nums);

        for (int num : nums) {
            System.out.print(num + "-");
        }
    }
}

0 赞同 0 条回复

y 普通 2022年11月21日下午9:04

var exchange = function(nums) {
   let left = 0;
   let right = nums.length - 1;
   let temp;
   while (left < right) {
       if (nums[left] % 2 === 1) {
           left++;
       } else if (nums[right] % 2 === 0) {
           right--;
       } else {
           temp = nums[left];
           nums[left] = nums[right];
           nums[right] = temp;
       }
   }
   return nums;
};

时间O(n)
空间O(1)

0 赞同 0 条回复

天然普通 2022年11月21日下午9:02

双指针，奇偶交换，快排时间复杂度O(n)，空间复杂度O（1）还可用用两个数组专门去存奇偶数，然后再返回空间复杂度o(n)

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if not nums:return nums
        left , right = 0 , len(nums)-1
        while left < right:
            while left < right and nums[left]&1 !=0: left +=1
            while left < right and nums[right]&1 ==0: right -=1
            nums[left],nums[right] = nums[right],nums[left]
        return nums

0 赞同 0 条回复

你有点可爱喔普通 2022年11月21日下午3:47

class Solution {   
    public int[] exchange(int[] nums) {

        if (nums == null || nums.length == 0){
            return nums;
        }
        int left = 0;
        int right = nums.length-1;
        //快速排序的时间复杂度O(n)
        while (left < right){
            while (left < right && nums[left]%2 != 0){
                left++;
            }
            while (left < right && nums[right] % 2 == 0){
                right--;
            }
            //交换位置
            if (left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;

    }
}

0 赞同 0 条回复

lobort 普通 2022年11月19日下午8:43

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

快排应用使用位运算来判断奇偶运算会快点

0 赞同 0 条回复

大宝子冲永久会员 2022年11月19日下午8:26

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 == 0) right--;
             int a =nums[left];
             nums[left] =nums[right];
             nums[right] =a;
         }   
         return nums;

    }
}

快排时间复杂度O(n)
空间复杂度O（1）

0 赞同 0 条回复

派大星普通 2022年11月19日下午1:25

class Solution {
//时间复杂度O(n)
//空间复杂度O(1)
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length <= 1)return nums;
        int l = 0;
        int r = nums.length - 1;
        while(l < r){
            if(nums[l] % 2 == 0 && nums[r] % 2 == 1) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
            if(l < nums.length - 1 && nums[l] % 2 == 1) l++;
            if(r > 0 && nums[r] % 2 == 0) r--;
        }
        return nums;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月17日下午5:23

第一题
双指针

“`c++
class Solution {
public:
vector exchange(vector& nums) {
int i = 0;
int j = nums.size()-1;
while(i < j) { if(nums[i]%2 != 0) { i++; }else if(nums[j] % 2 == 0) j--; else { swap(nums[i], nums[j]); }

    }
    return nums;
}

};

“`

0 赞同 0 条回复

易水寒永久会员 2022年11月17日下午2:59

快排

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

    private void exchange(int i, int j, int[] nums) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

0 赞同 0 条回复

just 普通 2022年11月17日下午12:05

//双指针
class Solution {
public:
vector exchange(vector& nums) {
int l=0,r=nums.size()-1;
while(l<r){
while(l<r&&nums[l]%21) l++;
while(l<r&&nums[r]%20) r–;
if(l<r) swap(nums[l],nums[r]);
}
return nums;

};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月17日上午10:50

自己实现，双指针，时间复杂度O(N)空间复杂度O(1)

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 == 0 ){
                l++;
                r--;
            }else if(nums[l] % 2 == 0 && nums[r] % 2 == 0){
                r--;
            }else if(nums[l] % 2 != 0 && nums[r] % 2 != 0){
                l++;
            }else if(nums[l] % 2 == 0 || nums[r] % 2 != 0){
                int temp = nums[l] ^ nums[r];
                nums[l] = temp ^ nums[l++];
                nums[r] = temp ^ nums[r--];
            }
        }
        return nums;
    }
}

快排，优化思路

//快排
class Solution {
    public int[] exchange(int[] nums) {
        int 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--;
            if(l < r){
                int temp = nums[l] ^ nums[r];
                nums[l] = temp ^ nums[l++];
                nums[r] = temp ^ nums[r--];
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

T 普通 2022年11月17日上午8:39

class Solution {
    //左右指针分别去找偶数和奇数，然后交换位置
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l < r) {
            if(nums[l] % 2 == 0) {
                if(nums[r] % 2 == 1) {
                    int tmp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = tmp;
                } else {
                    r--;
                }
            } else {
                l++;
            }
        }
        return nums;
    }
}

0 赞同 0 条回复

感到自己好渺小普通 2022年11月17日上午12:17

class Solution {
    public int[] exchange(int[] nums) {
        //利用快排将数组中的奇数和偶数对调
       int i = 0;
       int j = nums.length - 1;
       while(i < j){
           while(i < nums.length && nums[i] % 2 == 1) i++;
           while(j >= 0 && nums[j] % 2 == 0) j--;
           if(i < j){
               int t = nums[i];
               nums[i] = nums[j];
               nums[j] = t;
           }
       }
       return nums;
    }
}

0 赞同 0 条回复

Error 普通 2022年11月16日下午11:02

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] % 2 != 0:
                l += 1
                continue
            if nums[r] % 2 == 0:
                r -= 1
                continue
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1


        return nums

时间复杂度 O(n)

0 赞同 0 条回复

青木普通 2022年11月16日下午8:09

/**
    第一个想法是冒泡排序的做法，但是超时了
    所以就用两个指针指向左右端，当左右端分别为偶数/奇数时交换数值就可以了

    时间O(n)
    空间O(1)
 */

class Solution {
    public int[] exchange(int[] nums) {
        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--;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午7:56

时间复杂度为O（n），空间复杂度为O（1）

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] & 1) != 0)) left++;
            while(left < right && ((nums[right] & 1) != 1) ) right--;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }
}

0 赞同 0 条回复

So 普通 2022年11月16日下午7:51

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

时间：O(n)，空间：O(1)

0 赞同 0 条回复

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

共以下 29 个回答

双指针

# 回答此问题取消回复

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

共以下 29 个回答

双指针

# 回答此问题 取消回复

# 回答此问题取消回复