西安建设学院网站首页,宣传片制作软件app,网站排序,腾讯云 win wordpress题目#xff1a;
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入:…题目
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums [0]
输出: [0] 提示:
1 nums.length 104-231 nums[i] 231 - 1
解决
解法1
设置双指针ij。i遍历j指向非零元素。i遇到非零元素就把它挪到j所在位置同时j后移一位。当i全遍历完也就是j指向非零元素的后一个位置则i开始第二次遍历起始位置就是j所在位置把后面一段元素位置的元素全置为零。时间复杂度为O(n)。其实是i遍历了一遍j近似也遍历了一遍。
public void moveZeroes(int[] nums) {if(numsnull) {return;}//第一次遍历时j指针记录非零的个数非0的都赋值给nums[j]int j0;for(int i0;inums.length;i){if(nums[i]!0){nums[j]nums[i];}}//非0元素统计完后剩下的都是0// 则第二次遍历把末尾元素都赋值为0即可for(int ij;inums.length;i){nums[i]0;}} 解法2
官方题解。设置双指针但不是采取挪动方式而是用交换的方式左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。右指针不断向右移动每次右指针指向非零数则将左右指针对应的数交换同时左指针右移。则每次交换都是将左指针的零与右指针的非零数交换且非零数的相对位置未改变。
这样只用遍历一遍。但是这样的效率比挪动更低。
public void moveZeroes(int[] nums) {int n nums.length, left 0, right 0;while (right n) {if (nums[right] ! 0) {swap(nums, left, right);left;}right;}}public void swap(int[] nums, int left, int right) {int temp nums[left];nums[left] nums[right];nums[right] temp;
} 加油加油^_^
