双指针法解决力扣922题:按奇偶排序数组II的完整指南

深度学习
• 阅读 89

双指针法解决力扣922题:按奇偶排序数组II的完整指南

一、问题理解

题目要求将一个数组重新排序,使得:

  1. 所有偶数位于偶数索引位置(索引0,2,4...)
  2. 所有奇数位于奇数索引位置(索引1,3,5...)
  3. 不要求数字本身的排序,只需满足奇偶位置正确

二、解法思路

采用双指针法,分别维护两个指针

  • even指针:负责扫描偶数索引位置
  • odd指针:负责扫描奇数索引位置

当发现偶数索引位置是奇数,且奇数索引位置是偶数时,交换这两个位置的元素。

三、完整代码解析

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        int even = 0; // 偶数指针,初始指向第一个偶数位置(索引0)
        int odd = 1;  // 奇数指针,初始指向第一个奇数位置(索引1)

        while (even < n && odd < n) {
            // 找到偶数位置上不是偶数的元素
            while (even < n && nums[even] % 2 == 0) {
                even += 2;
            }
            // 找到奇数位置上不是奇数的元素
            while (odd < n && nums[odd] % 2 == 1) {
                odd += 2;
            }
            // 交换这两个位置上的元素
            if (even < n && odd < n) {
                swap(nums[even], nums[odd]);
            }
        }
        return nums;
    }
};

四、代码逐行解析

  1. evenodd指针初始化:分别指向第一个偶数和奇数索引位置
  2. 外层while循环:确保两个指针都在数组范围内
  3. 第一个内层while:跳过已经正确的偶数位置(即该位置已经是偶数)
  4. 第二个内层while:跳过已经正确的奇数位置(即该位置已经是奇数)
  5. swap操作:交换不满足条件的两个位置的元素

五、时间复杂度分析

  • 时间复杂度:O(n),每个元素最多被访问一次
  • 空间复杂度:O(1),只使用了常数级别的额外空间

六、常见错误

  1. 忘记检查指针越界条件
  2. 交换前没有验证指针有效性
  3. 错误理解奇偶索引和数值奇偶性的关系

来源:大矩学习资料

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
SQL 如何计算每个分组的中位数
中位数是指一组数据排序以后,位于中间位置的数据值。如果数据个数是奇数,中位数就是最中间位置那个值;如果是偶数,则是中间位置那两个数的平均值。怎么查询出数据分组以后每个组的中位数呢?用SQL来解决这个问题是很有难度的!SQL的集合是无序的,没有数据位置的概念,需要人为地造出行号,但是要对各分组独立编行号也困难。后来在SQL2003标准中加入了窗口函
BichonCode BichonCode
4年前
双指针问题
一、双指针之左右指针相关题目1.1题目要求:给定一个升序排列的整数数组,找到两个数,使它们的和等于给定的数,有且仅有一个满足条件的解,返回索引。题目分析:需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右
九路 九路
4年前
一个int数组,奇数排前,偶数排后,算法实现
//奇数排前,偶数排后publicstaticvoidsortOdd(intdata){intl0;intrdata.length1;while(l<r){while(l<r&&datar%20)
Wesley13 Wesley13
3年前
mysql之索引
一.索引:索引是表的目录,在查找内容之前可以先在目录中查找索引位置,以此快速定位查询数据。对于索引,会保存在额外的文件中1.1.创建一个索引:mysqlcreateindexix_classontb3(class_id);QueryOK,0rowsaffected(0.02sec)
Stella981 Stella981
3年前
Shell(希尔)排序
Shell(希尔)排序    对于直接插入排序而言,如果一个很小的数据单元位于很靠近右端的位置上,为了把这个数据单元移动到左边正确的位置上,中间所有的数据单元都需要向右移动一格。这个步骤对每一个数据项都执行了近n次复制。虽然不是所有的数据项都必须移动n个位置,但平均下来,每个数据项都会移动n/2格,总共是n\n/2次复制。因此,直接插入
贾蔷 贾蔷
3天前
力扣15题三数之和解法(C++双指针算法详解)
一、题目解读15题()要求在一个包含n个整数的中,找出所有三个数之和为0的组合,且每个组合的元素不能重复。题目考察数组遍历、与技巧的结合,是经典的多问题,对时间复杂度优化有较高要求。二、解题思路采用“双指针”策略:首先对原数组排序,然后固定第一个数,通过左
贾蔷 贾蔷
1个月前
洛谷P1168题终极解析:双堆法高效计算动态中位数 | 数据结构实战教程
一、问题理解与算法思路题目要求我们动态维护一个序列,并在每次读取奇数个数字时输出当前序列的中位数。这道题考察了两个核心算法点:堆数据结构的应用和中位数的高效计算。我们采用双堆法(一个大根堆和一个小根堆)来高效解决这个问题。‌解题关键步骤‌:使用大根堆存储较
贾蔷 贾蔷
3星期前
动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解
一、问题理解题目要求找出中满足特定条件的"好下标":对于下标i,其左侧k个元素必须是非递增的,右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。二、解题思路1.预处理核心思想是通过两次预处理:left数组:记录每个位置向左的非长度right数组:
深度学习 深度学习
1星期前
LeetCode 2576题解:双指针法求解最多标记下标(排序+贪心策略)
一、题目解读2576题要求在一个整数中寻找最多可标记的下标对:若nums法”的组合思路:1.排序预处理:对原数组nums进行升序排序,确保相同元素聚集,便于后续配对。2.双划分:将排序后的数组分为左右两半(左指针left0,右指针rightn/2),从
深度学习 深度学习
3天前
(NOIP2012提高组)洛谷P1080题解:用贪心策略解决国王游戏
一、问题分析这道题目要求我们安排大臣的排列顺序,使得获得最多金币的大臣获得的金币尽可能少。关键在于找到正确的规则,并处理大数相乘和相除的问题。二、解题思路1.‌排序规则确定‌:通过数学推导得出,应该按照左右手数字乘积从小到大排序1.‌处理‌:由于数字可能很