开始准备算法面试，毕竟马上找工作。将最近自己在leetcode做的题目记录一下，方便自己复习。同时也提供给有需要的朋友，https://leetcode.com/还没账号的朋友赶快去注册一个吧。
内容将包括：自己第一遍做的想法和类比其他人的优化。
优化主要是参考：慕课网一个实战课程：http://coding.imooc.com/class/82.html。感兴趣的可以看一下
正文：
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
You must do this in-place without making a copy of the array.Minimize the total number of operations. 题目读完了说白了就是给你一个数组，将数组中非零元素按照顺序不变的往前放，是零的往后放。
我的思路和实现：遍历整个nums数组，当遇到0元素将其删除，并单独开辟一个数组nums1，用来保存当前的数组有多少个0元素，最后将nums补齐。
注意:对vector中erase()的使用。ite = erase()使用必须更新这个迭代器，不然下次将使用这个无效的迭代器进行判断。
class Solution { public: void moveZeroes(vector<int>& nums) { vector<int> nums1; for (auto i = nums.begin(); i != nums.end();) { if ((*i) == 0) { //erase(p)---删除迭代器p所指定的元素，返回一个指向被删除元素之后元素的迭代器 i = nums.erase(i);//若p指向尾元素，返回off-the-end迭代器。若p指向尾后迭代器，则函数行为未定义 nums1.push_back(0); } else//之所以需要判断是因为当erase成功之后已经相当于i++，否则将加两次 { i++; } //删除以下这个判断是可以正常运行的，但是在leetcode运行时间反而增加了？？？ if (i == nums.end()) { break; } } for (auto i = nums1.begin(); i != nums1.end(); i++) { nums.push_back(*i); } } };优化一：
这里的空间复杂度为O(n)，其实就是统计有多少个0，我们可以将其变为：
int count = 0; for (auto i = nums.begin(); i != nums.end();) { if ((*i) == 0) { //erase(p)---删除迭代器p所指定的元素，返回一个指向被删除元素之后元素的迭代器 i = nums.erase(i);//若p指向尾元素，返回off-the-end迭代器。若p指向尾后迭代器，则函数行为未定义 count++; } else//之所以需要判断是因为当erase成功之后已经相当于i++，否则将加两次 { i++; } //删除以下这个判断是可以正常运行的，但是在leetcode运行时间反而增加了？？？ if (i == nums.end()) { break; } } for (auto i = 0; i <count ; i++) { nums.push_back(0); } 优化二：这里给出不用erase()操作的方式。
这个思路和我的方法一致。
// 时间复杂度 O(n) // 空间复杂度 O(n) void moveZeroes(vector<int>& nums) { vector<int> nonZeroElements; // 将vec中所有非0元素放入nonZeroElements中 for( int i = 0 ; i < nums.size() ; i ++ ) if( nums[i] ) nonZeroElements.push_back( nums[i] ); // 将nonZeroElements中的所有元素依次放入到nums开始的位置 for( int i = 0 ; i < nonZeroElements.size() ; i ++ ) nums[i] = nonZeroElements[i]; // 将nums剩余的位置放置为0 for( int i = nonZeroElements.size() ; i < nums.size() ; i ++ ) nums[i] = 0; }这个思路就是，设置两个索引，不需要单独开辟空间。将整个数组nums遍历，将[0...i]中所有的非零元素放入[0...k)中，注意是左闭右开。相当于记录有多少个非零元素，和我的优化一差不多。 // 时间复杂度 O(n) // 空间复杂度 O(1) void moveZeroes(vector<int>& nums) { int k = 0; // nums中, [0...k)的元素均为非0元素 // 遍历到第i个元素后,保证[0...i]中所有非0元素 // 都按照顺序排列在[0...k)中 for(int i = 0 ; i < nums.size() ; i ++ ) if( nums[i] ) nums[k++] = nums[i]; // 将nums剩余的位置放置为0 for( int i = k ; i < nums.size() ; i ++ ) nums[i] = 0; }以上都是需要两轮for循环来完成。以下就是只需要一轮for循环。
当遇到的元素是非零值，交换当前的元素位置，到放入到[0...k)中，
// 时间复杂度 O(n) // 空间复杂度 O(1) void moveZeroes(vector<int>& nums) { int k = 0; // nums中, [0...k)的元素均为非0元素 // 遍历到第i个元素后,保证[0...i]中所有非0元素 // 都按照顺序排列在[0...k)中 // 同时, [k...i] 为0 for(int i = 0 ; i < nums.size() ; i ++ ) if( nums[i] ) swap( nums[k++] , nums[i] ); }
//对于以上算法还可以有个优化，如果输入的全部是非零元素，那么上边的算法就会将所有的元素自己和自己交换一次。
所以只有当i！=k的时候，进行交换操作，当i==k时，直接k++，i++跳过
// 时间复杂度 O(n) // 空间复杂度 O(1) void moveZeroes(vector<int>& nums) { int k = 0; // nums中, [0...k)的元素均为非0元素 // 遍历到第i个元素后,保证[0...i]中所有非0元素 // 都按照顺序排列在[0...k)中 // 同时, [k...i] 为0 for(int i = 0 ; i < nums.size() ; i ++ ) if( nums[i] ) if( k != i ) swap( nums[k++] , nums[i] ); else k ++; }然而将上述算法，运行在leetcode上，发现和我的思路算法的运行时间一致
