算法笔记_面试题_2.移动零(将数组的的0元素移到末尾)

悠悠 2023-02-20 02:55 66阅读 0赞

# 问题 #

[283. 移动零][283.]

给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

## **示例:** ##

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

## **说明**: ##

1.  必须在原数组上操作，不能拷贝额外的数组。
2.  尽量减少操作次数。

# 分析 #

*  使用交换0和非0元素的方式，实现所有0都到末尾。
 *  关键点在于确定什么时候交换。

# 最优解之一： #

说明： 索引i用来遍历数组；索引j用来“始终”指向0元素的位置，j在交换过之后，直接+1，使其一直指向0的元素。特殊情况在于初始位置（i=0, j=0）时，如数组arr若是\[7,0,3,0,9\]时，第一次交换arr\[i=0\] 和arr\[j=0\],即自己跟自己交换了下，交换完后，j=j+1指向了0的元素位置。区别与[去除有序数组中重复元素的算法][Link 1]：这里是：1）比较是否等0；2）不等0就先交换；3）再移动指针（索引j）。 去除有序数组中重复元素的算法是1）比较与前一个元素是否相等，2）不等先移动指针（索引j），3）再直接覆盖重复元素。

## 动画演示： ##

![2020070818385525.gif][]

## 代码： ##

#include <stdio.h>
    #include <iostream>
    #include <vector>
    
    void moveZeroToEnd(std::vector<int>& nums)
    {
    	int j = 0;
    	int tmp = 0;
    	for (int i = 0; i < nums.size(); ++i)
    	{
    		if (nums[i] != 0)
    		{
    			tmp = nums[i];
    			nums[i] = nums[j];
    			nums[j] = tmp;
    			++j;
    		}
    	}
    }

测试：

int main(int argc, char* argv[])
    {
    	std::vector<int> ver = { 0,7,3,0,9 };
    	moveZeroToEnd(ver);
    	for (int i = 0; i < ver.size(); ++i)
    	{
    		std::cout << ver[i] << " ";
    	}
    	return 0;
    }

输出结果：

![20200622184828428.png][]

注意：Ubuntu16.04下默认使用的g++ 使用的是c++98规范, 不支持vector的直接赋值初始化。需修改~/.bashrc文件

参考：[https://blog.csdn.net/midi666/article/details/83151729][https_blog.csdn.net_midi666_article_details_83151729]

# 时间复杂度分析： #

因为这里只用到了交换，所以时间复杂度是O(n), 空间复杂度没有用到数组相关，所以是O(1).

参考：[极客时间][Link 2]

力扣： [https://leetcode-cn.com/problems/move-zeroes/][283.]

[283.]: https://leetcode-cn.com/problems/move-zeroes/
[Link 1]: https://blog.csdn.net/shyjhyp11/article/details/106911818
[2020070818385525.gif]: https://img-blog.csdnimg.cn/2020070818385525.gif
[20200622184828428.png]: https://img-blog.csdnimg.cn/20200622184828428.png
[https_blog.csdn.net_midi666_article_details_83151729]: https://blog.csdn.net/midi666/article/details/83151729
[Link 2]: https://u.geekbang.org/lesson/15?article=213890&utm_source=time_web&utm_medium=menu&utm_term=timewebmenu