力扣最热一百题——4.移动零

目次
日常吐槽
题目链接：283. 移动零 - 力扣（LeetCode）
题目形貌
示例
提示

解法一：交换位置
思路
代码实现
解法二：覆写元素
思路
代码实现
总结

---

---

日常吐槽

        本日原来是筹划玩玩游戏的，结果我直接上头了，输一把赢一把的，唉，最后也没法从完善B+差三分上A，还到欠了四十多分才上A，我真的服了，话不多说直接上本日的题目吧。

---

题目链接：283. 移动零 - 力扣（LeetCode）

注：下述题目形貌和示例均来独立扣
题目形貌

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末端，同时保持非零元素的相对顺序。
请留意 ，必须在不复制数组的环境下原地对数组进行操作。

示例

示例 1:

1. <strong>输入:</strong> nums = [0,1,0,3,12]
2. <strong>输出:</strong> [1,3,12,0,0]

复制代码

示例 2:

1. <strong>输入:</strong> nums = [0]
2. <strong>输出:</strong> [0]

复制代码

提示

• 1 <= nums.length <= 104
  
• -231 <= nums <= 231 - 1
  

进阶：你能只管淘汰完成的操作次数吗？
呃不能。。。。。

---

        这里题目有一个很关键的信息就是要在不复制数组的环境下对数组进行操作，也就是我们要在原数组上进行操作，不能新开一个数组，否则就太简单了，直接遍历一遍不要0就行了。而且记住要保持其他元素的相对顺序。


解法一：交换位置

思路

        这个解法的思路就是我每次先找到一个0，这个0的位置是最靠前的一个0，然后在这个0的位置上往后找第一个不为零的元素，使用两个指针记录这两个数的位置，交换他们的位置即可，非常简单，思路也是很清晰的，交换完最后一个0之后，所有的0也就在后面了。
代码实现

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3.         // 0,1,0,3,12
4.         // l r
5.         // 1,0,0,3,12
6.         //  lr
7.         // 1,3,12,0,0
8.         //      l   r
9.         // 获取数组的长度
10.         int len = nums.length;
11.         // 定义出两个指针
12.         int left = 0;
13.         int right = 1;
14.         // 进入寻找非0元素的过程
15.         // left记录0的位置，right记录第一个遇到的非零的位置
16.         while(left < len){
17.             // 结束特判
18.             if(right == len && nums[right - 1] == 0){
19.                 break;
20.             }
21.             if(nums[left] == 0){
22.                 while(right < len){
23.                     if(nums[right] != 0){
24.                         swap(nums,left,right);
25.                         left++;
26.                         right = left + 1;
27.                         break;
28.                     }else{
29.                         right++;
30.                     }
31.                 }
32.             }else{
33.                 left++;
34.                 right++;
35.             }
36.         }
37.     }
40.     /**
41.         交换数组位置
42.     */
43.     public void swap(int[] arr,int left,int right){
44.         int temp = arr[left];
45.         arr[left] = arr[right];
46.         arr[right] = temp;
47.     }
48. }

复制代码

        说实话，虽然说这个方法比较好思考出来，但是利于人脑思考的方法终极的结果都是不尽人意的。

---

解法二：覆写元素

思路

       这个解法的思路是将数组中的所有0移动到数组的末端，而保持非零元素的相对顺序不变。
        起首，定义两个指针 left 和 right，初始时都指向数组的开头。right 指针用于遍历数组，left 指针用于记录下一个非零元素应该存放的位置。
        然后，开始遍历数组，当 right 指针指向的元素为0时，right 指针向右移动一位，跳过该次循环。这是因为我们要将所有的0移动到数组的末端，所以需要忽略所有的0。
        当 right 指针指向的元素不为0时，将该元素覆盖到 left 指针指向的位置，并将 left 指针向右移动一位，即 left++。如许，非零元素就被移动到了正确的位置上。
        循环结束后，left 指针后面的元素都应该是0，所以我们再次遍历数组，将 left 指针后面的元素都设置为0。
        终极的结果就是将所有的0移动到了数组的末端，而非零元素的相对顺序保持不变。

代码实现

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3.         int left = 0;
4.         int right = 0;
5.         while(right < nums.length){
6.             if(nums[right] == 0){
7.                 //这里就是right指针遇到0了
8.                 //需要跳过这个数和跳过这次循环
9.                 right++;
10.                 continue;
11.             }
12.             //这里进行覆盖操作
13.             nums[left++] = nums[right++];
14.         }
15.         while(left < nums.length){
16.             nums[left++] = 0;
17.         }
18.     }
19. }

复制代码

        这个方法的执行效率和内存开销直接起飞了bro，遥遥领先。

总结

        官方题解我以为写得非常的难以理解，但是他确实是把交换的思路优化到极致了，以至于执行效率照旧很快，所以这个世界上的万千代码和人一样，厉害的，你更难以洞察其心田。




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。