临沂电商网站建设,网页设计与网站建设实训报告,北京南站地图,河北中小企业网站题目#xff1a; 给定一个整数数组 nums#xff0c;编写一个算法将所有的0移到数组的末尾#xff0c;同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 注意#xff1a;必须在原数组上操作#xff0c;不能拷贝额外的数组。尽量减少操作次数。 这…
题目 给定一个整数数组 nums编写一个算法将所有的0移到数组的末尾同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 注意必须在原数组上操作不能拷贝额外的数组。尽量减少操作次数。 这个问题考察候选人处理数组的能力以及他们编写高效、优雅代码的能力。在解决问题时请考虑如何避免不必要的元素移动。
思路
1、双指针法 使用两个指针一个用来遍历数组遍历指针另一个指向最新发现的非零元素应当存放的位置非零指针。 当遍历指针指向的值不为0时将其与非零指针指向的值交换然后非零指针前移。 通过整个数组的遍历所有非零元素都被推向数组的开头而0都被留在了数组的末尾。2、计数零元素法 首先遍历一次数组统计出0的个数。 在第二次遍历期间使用一个新的索引比如 insertPos它基于0的计数从数组开头开始移动。 如果遍历到非零元素就将它放到insertPos的位置并将insertPos向前移动。 遍历完成后按照统计出的0的个数在数组末尾补上0。3、移动非零元素法 遍历数组一旦遇到非0数就将其移到数组最前方现有非0数的后面。 记录最后一个非0数的位置。 在数组剩余的部分填充0。 每种方法都有其特点但双指针法在空间和操作复杂度上通常是最优的。这个方法只需要( O(n) )的时间复杂度和( O(1) )的额外空间复杂度。
时间复杂度 1. **双指针法**时间复杂度为 ( O(n) )因为只需要遍历一遍数组n 为数组长度。 2. **计数零元素法**时间复杂度为 ( O(n) )即便需要两次遍历一次计数0的个数一次移动非零元素但两次遍历的时间复杂度都是线性的。 3. **移动非零元素法**时间复杂度也为 ( O(n) )一次线性遍历即可完成所有非零元素的移动和0的填充。 值得注意的是尽管所有方法的时间复杂度都是线性的但实际执行时间可能会因为常数因子和元素实际移动次数的差异而有所不同。在决定使用哪一种方法时这也是需要考虑的因素之一。
实现代码
1、双指针法
#include stdio.h
void moveZeroes(int* nums, int numsSize) {int j 0; // 指向当前非0元素应该插入的位置for (int i 0; i numsSize; i) {if (nums[i] ! 0) {int temp nums[i];nums[i] nums[j];nums[j] temp;j;}}
}
2、计数零元素法
#include stdio.h
void moveZeroes(int* nums, int numsSize) {int zeroCount 0; // 计算数组中0的个数for (int i 0; i numsSize; i) {if (nums[i] 0) {zeroCount;}}int index 0;for (int i 0; i numsSize; i) {if (nums[i] ! 0) {nums[index] nums[i];}}for (int i index; i numsSize; i) {nums[i] 0;}
}
3、移动非零元素法
#include stdio.h
void moveZeroes(int* nums, int numsSize) {int insertPos 0; // 指向当前已处理数组的末尾for (int i 0; i numsSize; i) {if (nums[i] ! 0) {nums[insertPos] nums[i];}}while (insertPos numsSize) {nums[insertPos] 0;}
}
