每日一练2024.5.9

题目：

给定一个非负整数数组 nums， nums 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时， i 也是偶数。

你可以返回 任何满足上述条件的数组作为答案 。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

提示：

2 <= nums.length <= 2 * 104
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000

进阶：可以不使用额外空间解决问题吗？

解题：

这道题的目标是重新排序给定的非负整数数组nums，使数组满足特定的位置规则：位于偶数索引的元素是偶数，位于奇数索引的元素是奇数。根据题目的提示，我们知道数组长度是偶数，且一半元素是偶数，另一半是奇数。解决这个问题有几种方法：

两个指针法：利用两个指针，一个只在偶数索引移动，一个只在奇数索引移动。交换两个指针指向的不符合位置要求的数。
分类后重组：创建两个数组，一个存放所有的偶数，另一个存放所有的奇数，最后交替把它们重组到原数组中。

对于进阶问题：题目询问你是否能在不使用额外空间的情况下解决这个问题。可以运用第一种方法（两个指针法），因为这种方法不需要创建额外的数组，直接在原数组上进行操作即可。步骤大致如下：

初始化两个指针，evenIndex从0开始（用于偶数索引），oddIndex从1开始（用于奇数索引）。
遍历数组直至evenIndex或者oddIndex到达数组末尾。
当evenIndex指向的数字是奇数，且oddIndex指向的数字是偶数时，则交换这两个数。
如果evenIndex指向的数字已经是偶数，则evenIndex增加2；同理，如果oddIndex指向的数字是奇数，则oddIndex增加2。
重复步骤3和4，直到整个数组被正确排序。

实现这个算法，只需要在原数组上进行指针移动和元素交换操作，不会占用除输入数组以外的额外空间，因此是一个原地排序算法。

代码：

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int evenIndex = 0; // 偶数索引
        int oddIndex = 1;  // 奇数索引

        while (evenIndex < n && oddIndex < n) {
            // 寻找错位的偶数索引
            while (evenIndex < n && nums[evenIndex] % 2 == 0) {
                evenIndex += 2;
            }

            // 寻找错位的奇数索引
            while (oddIndex < n && nums[oddIndex] % 2 != 0) {
                oddIndex += 2;
            }

            // 交换
            if (evenIndex < n && oddIndex < n) {
                int temp = nums[evenIndex];
                nums[evenIndex] = nums[oddIndex];
                nums[oddIndex] = temp;
            }
        }

        return nums;
    }
}

知识点概览：

这段代码是为了解决一个特定的问题，即在给定的非负整数数组中，按照特定规则重新排序数组，使偶数索引处的元素为偶数，奇数索引处的元素为奇数。这个问题的解决方法采用了就地排序的策略，意味着不需要额外的数组来存储结果，而是直接在输入数组上操作。这里用到的主要Java编程知识点包括：

数组：使用数组来存储输入的整数序列。数组是一种基本的数据结构，支持通过索引快速访问元素。
变量：定义了几个整型变量（n，evenIndex，oddIndex）用于存储数组长度和控制循环中的索引位置。
循环控制（while循环和嵌套while循环）：使用两层while循环来遍历数组并找到需要交换的元素位置。外层循环控制整个过程直到所有元素被正确排序，内层循环分别找到不在正确位置的偶数元素和奇数元素。
条件判断（if语句）：利用if语句和求余运算符%来检查元素是否符合其索引的奇偶性要求。
算术运算：使用%求余运算符来判断数字的奇偶性（偶数 % 2 == 0，奇数 % 2 != 0）。
变量交换：在找到不符合位置要求的一对偶数索引和奇数索引的元素后，通过临时变量temp执行数组内元素的交换。
空间复杂度控制：这个解决方案遵循就地操作的原则，除了原数组以外，不需要分配额外的空间来存储数据或结果，因此空间复杂度为O(1)。
索引控制：通过精确地控制evenIndex和oddIndex，保证了即使发生了交换操作，也能再次回到循环中继续寻找下一个不在正确位置上的元素。这里的索引控制确保了算法的完整性和效率。

知识点类别	描述
数组	使用数组存储输入的整数序列，支持通过索引快速访问元素。
变量	定义整型变量（例如`n`，`evenIndex`，`oddIndex`）来存储数组长度和控制索引位置。
循环控制	使用while循环及嵌套while循环遍历数组并查找需要交换的元素位置。外层循环控制整个过程，内层循环分别寻找错位的偶数和奇数元素。
条件判断	利用if语句合并求余运算符`%`判断元素与其索引奇偶性是否匹配。
算术运算	使用`%`求余运算符判断数字的奇偶性（偶数为`% 2 == 0`，奇数为`% 2 != 0`）。
变量交换	在找到不符合位置要求的元素对时，通过临时变量`temp`执行数组内的元素交换。
空间复杂度控制	整个算法运行过程中，除原数组外没有使用额外的存储空间，空间复杂度为O(1)。
索引控制	精确控制`evenIndex`和`oddIndex`确保算法能继续寻找不在正确位置的元素，这种控制方式保证了算法的完整性和效率。