408算法题leetcode--第七天
283. 移动零
- 283. 移动零
- 思路:代码中注释阐述
- 时间:O(n);空间:O(1)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 简单思路:用一个辅助数组,将非0元素复制到里面
// 双指针,一个p指向结果数组,一个q指向原数组
// q找到非0元素,移动到p中
int p = 0, q = 0;
int size = nums.size();
while(q < size){
if(nums[q] != 0){
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
++p;
}
++q;
}
}
};
88. 合并两个有序数组
- 88. 合并两个有序数组
- 思路:如注释
- 时间:O(m + n);空间:O(1)
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 逆序双指针:123000 456 > 123006 > 123056 > 123456
int p = m - 1, q = n - 1;
int tail = m + n - 1; // 存放于nums1的最后的位置
while(p >= 0 && q >= 0){
if(nums1[p] > nums2[q]){
nums1[tail--] = nums1[p--];
} else {
nums1[tail--] = nums2[q--];
}
}
while(q >= 0){
nums1[tail--] = nums2[q--];
}
}
};
原文地址:https://blog.csdn.net/weixin_58073817/article/details/142321716
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!