力扣传送:
https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
给一个排好序的链表,删除把链表中出现的所有的重复的项:
1 2 2 3 3 3 4 5 ----->1 4 5
这道题有很多种解法,我第一眼看到这题的时候,想到了 哈希表。
利用哈希表来记录出现的重复的节点元素,接着在遍历链表,等到这个节点出现在了哈希表中,则while 循环一直跳过这个节点,直到跳到下一个不同的元素为止。
哈希表的做法:
class Solution {public:
ListNode* deleteDuplicates(ListNode* head) {unordered_mapm;
ListNode* temp=head;
while (temp)
{ //首先初始化哈希表,记录下每个节点的值出现的次数
m[temp->val]++;
temp=temp->next;
}
ListNode* pDummy=new ListNode{-101,head};
ListNode* slow=pDummy;
ListNode* fast=head;
while (fast && fast->next)
{if (m[fast->val]>1)
{ListNode* pTemp=fast->next;
while (fast && m[fast->val]>1)
{fast=fast->next;
}
slow->next=fast;
}
else
{slow=slow->next;
fast=fast->next;
}
}
return pDummy->next;
}
};
哈希表的缺点:
我们的哈希表的空间随着链表的增大而增大,空间复杂度达到了O(N)。
但其实我们没必要使用哈希表。
我们知道用哈希表来记录出现次数大于一次的节点,那我们能不能直接用双指针的快指针来记录呢? 只需要合适的边界检测,就可以记录下其快指针的 当前节点元素和 下一个节点元素的值,判断他们是否相等即可。
实现:
class Solution {public:
ListNode* deleteDuplicates(ListNode* head) {ListNode* pDummy=new ListNode{-101,head};
ListNode* slow=pDummy;
ListNode* fast=head;
while (fast && fast->next)
{int val=fast->val;
if (val==fast->next->val)
{while (fast && fast->val==val)
{fast=fast->next;
}
slow->next=fast;
}
else
{slow=fast;
fast=fast->next;
}
}
return pDummy->next;
}
};
时间复杂度:O(N)只遍历链表一遍,空间复杂度:O(1)
力扣传送门:
https://leetcode.cn/problems/3sum/description/?envType=study-plan&id=suan-fa-ji-chu&plan=algorithms&plan_progress=y00ve32
找到数组中是否包含三个元素使得 nums[i]+nums[j]+nums[z] =0
这道题目一看看出就可以使用暴力搜索的做法:首先给数组排序,然后创建一个三重循环,每重循环遍历每一个元素;注意,我们的元素可能会出现重复项,因此我们要跳过两重循环中可能遍历到的重复的项:
class Solution {public:
vector>threeSum(vector& nums) {vector>res;
int n=nums.size();
sort(nums.begin(),nums.end());
for (int i=0;iif (i==0 || nums[i]!=nums[i-1])
{for (int j=i+1;jif (j==i+1 || nums[j]!=nums[j-1])
{for (int z=j+1;zif (z==j+1 || nums[z]!=nums[z-1])
{ if (nums[i]+nums[j]+nums[z]==0)
{res.push_back({nums[i],nums[j],nums[z]});
}
}
}
}
}
}
}
return res;
}
};
我们的时间复杂度达到了O(N^3) 这对于最长数据量3000来说是很容易超时的,因为 3000 * 3000 * 3000 相乘后达到了27,000,000,000,即这就是三重循环的最坏的情况,因此暴力搜索的方法无法通过。
我们引入一个新方法:
利用双指针降低维数: 利用双指针把三重循环降低为二重循环。
我们就可以保持第二重循环不变,而将第三重循环变成一个从数组最右端开始向左移动的指针
class Solution {public:
vector>threeSum(vector& nums) {int n=nums.size();
vector>res;
sort(nums.begin(),nums.end());
for (int i=0;i//当前项和前一项相同,则当前数字已经被刚才用过了,则直接跳过这个数字
if (i>0 && nums[i]==nums[i-1])
{continue;
}
//第二重循环同时遍历 j 和 z
int z=n-1; //初始化z的位置,z从后往前
for (int j=i+1;j//同理,跳过重复的数字
if (j>i+1 && nums[j]==nums[j-1])
{continue;
}
//同时需要保证j0)
{//因为序列从小到大排序,当前的结果大于0,则减小z,寻找合适的位置
--z;
}
//如果j 和 z相遇,则表示无论j再往后,z再往前,他们都不可能再有结果了(和为0),因为j再往后遍历的数字一定和z之前的一个数字相同; z也是,一定和j之前的一个数字相同,我们已经遍历过了,所以这种情况直接退出
if (j==z)
{break;
}
if (nums[i]+nums[j]+nums[z]==0)
{res.push_back({nums[i],nums[j],nums[z]});
}
}
}
return res;
}
};
总结:
当我们需要枚举数组中的两个元素时,如果我们发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法,将枚举的时间复杂度从 O(N^2)减少至 O(N)
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻标题:算法进阶:双指针(一)c++leetcode例题-创新互联
文章源于:https://www.cdcxhl.com/article6/pieig.html
成都网站建设公司_创新互联,为您提供Google、网站制作、网站营销、网页设计公司、云服务器、品牌网站建设
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联