刷题笔记:力扣第283题-移动零

1.一道简单的双指针题目初步想法为设置两个快慢指针快指针遍历一遍数组将非0元素放到慢指针处之后慢指针遍历剩余元素并全部填充为0即可。完整代码如下1. void moveZeroes(int* nums, int numsSize) { 2. // l慢指针记录非零元素待存放位置r快指针遍历整个数组 3. int l 0, r 0; 4. // 快指针遍历所有元素 5. while (r numsSize){ 6. // 当前遍历到非零数字存入慢指针位置慢指针后移 7. if (nums[r] ! 0){ 8. nums[l] nums[r]; 9. } 10. // 快指针持续右移 11. r; 12. } 13. 14. // 慢指针之后剩余位置全部填充0 15. while (l numsSize) nums[l] 0; 16. 17. return; 18. }该算法时间复杂度为O(n)空间复杂度为O(1)。2.还可以让快指针一直后移找到第一个非零数后与慢指针交换这样能保证快指针和慢指针之间全是0最后它们能被顺利运动到数组末尾。完整代码如下1. // 交换两个整型变量的值 2. void swap(int* a, int* b){ 3. int tmp *a; 4. *a *b; 5. *b tmp; 6. } 7. 8. void moveZeroes(int* nums, int numsSize) { 9. // l记录下一个非零数字要放置的下标r遍历数组的快指针 10. int l 0, r 0; 11. // 快指针逐个遍历数组所有元素 12. while (r numsSize){ 13. // 找到非0元素和l位置元素交换交换后l向后移动一位 14. if (nums[r]){ 15. swap(nums[l], nums[r]); 16. } 17. // 快指针持续右移 18. r; 19. } 20. 21. return; 22. }该算法时间复杂度为O(n)空间复杂度为O(1)。