剑指 Offer 21. 调整数组顺序使奇数位于偶数前面【30】

深碍√TFBOYSˉ_ 2023-09-26 09:04 45阅读 0赞

**目录**

1.题目：调整数组顺序使奇数位于偶数前面

2.解题思路：

3.代码实现：

4.心得体会：

5.知识点补充：（经典排序之冒泡、快速排序）

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 11. 旋转数组的最小数字][Offer 11.]

> **力扣此题地址：**
> 
> [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）][Offer 21. _ - _LeetCode]

## 1.题目：调整数组顺序使奇数位于偶数前面 ##

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

**示例：**

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

## 2.解题思路： ##

这道题目最终可以得到一个这样的数组，左边的部分都是奇数，右边的部分都是偶数。

![8e24d8da83fd4edc9ad9664509e4577c.png][]

如上图所示，绿色部分都是奇数，黄色部分都是偶数，并且此时 left 指向了奇数的最后一个元素，right 指向了偶数的第一个元素。

为了得到这样一个结果，需要执行如下的操作：

>  *  1、设置两个指针 left 和 right，left 指向当前区间的最左侧元素，right 指向当前区间的最右侧元素。
>  *  2、left 向右移动，right 向左移动，并且要使得 left 左边的元素（包含 left 本身）都是奇数，right 右边的元素（包含 right 本身）都是偶数。
>  *  3、如果 left 指针指向的元素值是奇数，那么说明该元素在左侧了，观察其它的元素，即让 left 向右移动。
>  *  4、如果 right 指针指向的元素值是偶数，那么说明该元素在右侧了，观察其它的元素，即让 right 向左移动。
>  *  5、否则就说明，此时要么 left 指向的元素值为偶数，要么 right 指向的元素值为奇数，它们不在正确的位置上，需要交换一下。

## 3.代码实现： ##

class Solution {
        public int[] exchange(int[] nums) {
            
            //定义头指针left
            int left = 0;
            //定义尾指针right
            int right = nums.length-1;
            //定义临时变量temp
            int temp;
    
            //移动left和right，直到left在right右侧或相遇为止
            while(left <right){
    
                //如果左边是偶数，右边是奇数，则交换位置
                if(nums[left] % 2 ==0 && nums[right] % 2 == 1){
                    temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    left++;
                    right--;
                }
                //如果左边是奇数，右边是偶数，左指针向右移动
                else if(nums[left] % 2 ==1 && nums[right] % 2 == 1){
                    left++;
                }
                //如果左边是偶数，右边也是偶数，则右指针向左移动
                else if(nums[left] % 2 ==0 && nums[right] % 2 == 0){
                    right--;
                }
                //否则，左指针指向奇数，右指针指向偶数，则左指针向右移动，右指针向左移动
                else{
                    left++;
                    right--;
                }
            }
            return nums;
        }
    }

## 4.心得体会： ##

> **思路：**
> 
> 一开始看到这道题的时候，我有两个思路，一个是从头到尾遍历一遍，像冒泡排序似的[（冒泡排序算法）][Link 1]，前后两个元素（前偶数后奇数）交换位置。后面考虑了一下时间复杂度，想着这样肯定不行。后面又想到了和题解思路类似的思路，类似于快速排序[（快速排序算法）][Link 2]，就是数组前后各设置一个指针，然后进行交换。大致思路是想通了，但是一些实现细节还是有点差别。
> 
> **实现：**
> 
> 这道题还是比较简单的，只要把思路理清晰了，按照思路把代码写出来，没什么难度。不过确实有感觉到一点，随着题刷的越多，对解题的思路也提升很多。

## 5.知识点补充：（经典排序之冒泡、快速排序） ##

> [快速排序算法][Link 2]
> 
> [冒泡排序算法][Link 1]

[Offer 11.]: https://blog.csdn.net/m0_51697147/article/details/127072459?spm=1001.2014.3001.5501
[Offer 21. _ - _LeetCode]: https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
[8e24d8da83fd4edc9ad9664509e4577c.png]: https://img-blog.csdnimg.cn/8e24d8da83fd4edc9ad9664509e4577c.png
[Link 1]: https://blog.csdn.net/m0_51697147/article/details/124911555
[Link 2]: https://blog.csdn.net/m0_51697147/article/details/124943618