本文主要是介绍每日一练2024.5.10,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
给定一个非负整数数组 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 确保算法能继续寻找不在正确位置的元素,这种控制方式保证了算法的完整性和效率。 |
2024.5.10
这篇关于每日一练2024.5.10的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!