题目要求:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/move-zeroes
解题代码:
#include <iostream> #include <vector> using namespace std; class Solution { public: // 时间复杂度:O(n) // 空间复杂度:O(n) void moveZeroes(vector<int>& nums) { vector<int> nonZeroElements; // 提取非零的元素 for (int i = 0; i < nums.size(); i++) { if (nums[i]) nonZeroElements.push_back(nums[i]); } // 将非零的元素按顺序赋值给原有的数组 for (int i = 0; i < nonZeroElements.size(); i++) nums[i] = nonZeroElements[i]; // 将其他元素的值修改为0 for (int i = nonZeroElements.size(); i < nums.size(); i++) nums[i] = 0; } }; int main() { int arr[] = {0, 1, 0, 3, 12}; vector<int> vec(arr, arr + sizeof(arr)/ sizeof(int)); Solution().moveZeroes(vec); for (int i = 0; i < vec.size(); i++) cout<<vec[i]<<" "; cout<<endl; return 0; }
不使用中间变量的解法:
class Solution { public: // 时间复杂度: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; } } };
一次循环解决问题:
class Solution { public: // 时间复杂度: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 (i != k) swap(nums[k++], nums[i]); // nums[k]与nums[i]进行值的交换 else k++; } } } };