题目及分析
题目
给定一个数组 nums, 编写一个函数将所有 0 移动到数组的末尾, 同时保持非零元素的相对顺序.
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作, 不能拷贝额外的数组.
尽量减少操作次数.
分析
题目需要注意的地方: 必须在原来的数组操作, 说明限制空间复杂度限制为 O(1).
题目意思比较明确: 将 0 移动到数组的末尾. 但是不能有额外数组. 所以单数组里面移动, 可以使用交换的方式.
需要理解什么与什么进行交换. 不仅仅是非 0 数字和 0 数字进行交换. 交换的是将非 0 的数字通过交换进入了非 0 的区域里面.
所以需要定义的是非 0 的范围 [0,nonZeroIndex), 表示在[0,nonZeroIndex) 左闭右开里面是非 0 数的范围.
结果示例
- class Solution {
- public void moveZeroes(int[] nums) {
- int nonZeroIndex = 0;//[0,nonZeroIndex)为非 0 的范围
- for(int i=0;i<nums.length;i++){
- if(nums[i] !=0){
- swap(i,nonZeroIndex,nums);// 交换非 0 数到非 0 范围里面.
- nonZeroIndex++;// 非 0 区域扩大
- }
- }
- }
- private void swap(int a,int b,int[] nums){
- int temp = nums[a];
- nums[a] = nums[b];
- nums[b] = temp;
- }
- }
特殊场景优化
这里可能的特殊场景为 nums 数组里面全为非 0 的数字, 这样每一次都是自己与自己进行交换操作. 如果需要考虑这种极端场景的话, 就需要加多一步判断.
- // 考虑极端条件 nums 全部为非 0 时候,
- if(i != nonZeroIndex) {
- swap(i,nonZeroIndex,nums);// 交换非 0 数到非 0 范围里面.
- nonZeroIndex++;// 非 0 区域扩大
- }else{
- nonZeroIndex++;
- }
这样场景的代码为:
- class Solution {
- public void moveZeroes(int[] nums) {
- int nonZeroIndex = 0;//[0,nonZeroIndex)为非 0 的范围
- for(int i=0;i<nums.length;i++){
- if(nums[i] !=0){
- // 考虑极端条件 nums 全部为非 0 时候
- if(i != nonZeroIndex) {
- swap(i,nonZeroIndex,nums);// 交换非 0 数到非 0 范围里面.
- nonZeroIndex++;// 非 0 区域扩大
- }else{
- nonZeroIndex++;
- }
- }
- }
- }
- private void swap(int a,int b,int[] nums){
- int temp = nums[a];
- nums[a] = nums[b];
- nums[b] = temp;
- }
- }
来源: http://www.bubuko.com/infodetail-3386709.html