丰和园林建设集团网站,百度问答首页,学编程的软件,怎么建网站赚钱1.两数之和 思路分析1#xff08;暴力法#xff09;
双重循环枚举满足num[i] nums[j] target的索引#xff0c;刚开始不知道如何返回一对索引。后来知道可以直接通过return {i,j}返回索引#xff1b;注意#xff1a;j应该从i1处开始#xff0c;避免使用两次相同的元素…1.两数之和 思路分析1暴力法
双重循环枚举满足num[i] nums[j] target的索引刚开始不知道如何返回一对索引。后来知道可以直接通过return {i,j}返回索引注意j应该从i1处开始避免使用两次相同的元素如果没有找到则需要返回空return{};时间复杂度 o ( N 2 ) , o(N^2), o(N2),其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
具体实现代码详解版
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int l nums.size(); // 获取数组的长度// 外层循环遍历数组中的每个元素for (int i 0; i l; i) {// 内层循环从下一个元素开始遍历for (int j i 1; j l; j) {// 检查当前两个元素的和是否等于目标值if (nums[i] nums[j] target) {// 如果找到了返回这两个元素的索引return {i, j};}}}// 如果没有找到满足条件的元素返回空的 vectorreturn {};}
};
思路分析2哈希表优化
遍历数组对每个元素 nums[i]计算它的补数 target - nums[i];查找补数使用 hashtable.find() 方法检查补数是否已存在于哈希表中;返回索引如果找到了补数就返回补数的索引和当前索引i;更新哈希表如果未找到补数则将当前元素及其索引存入哈希表
样例模拟
对于 nums [2, 7, 11, 15] 和 target 9我们使用twoSum 函数来找到两个数的索引使它们的和等于目标值。 1.第一轮迭代(i 0)
当前元素 nums[0] 2补数为 9 - 2 7;哈希表中没有 7所以将 2 存入哈希表hashtable[2] 0;
2.第二轮迭代i 1):
当前元素 nums[1] 7补数为 9 - 7 2。在哈希表中找到 2其索引为 0;返回 {0, 1}表示 nums[0] 和 nums[1] 的和等于 9。
具体实现代码详解版
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hashtable; // 创建哈希表存储数字及其索引// 遍历数组中的每个元素for (int i 0; i nums.size(); i) {// 计算当前数字的补数int complement target - nums[i];// 在哈希表中查找补数auto it hashtable.find(complement);if (it ! hashtable.end()) {// 如果找到了补数返回其索引和当前索引return {it-second, i};}// 将当前数字及其索引存入哈希表hashtable[nums[i]] i;}// 如果没有找到返回空的 vectorreturn {};}
};2.字母异位词分组 思路分析1字母排序
理解字母异位词两个字符串互为字母异位词当且仅当两个字符串包含的字母相同。 需要根据特征进行归类就应该利用哈希表由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键哈希表的值为一组字母异位词列表。 哈希表使用 unordered_map 来存储排序后的字符串作为键原字符串作为值的列表。 字符串排序通过排序将字母异位词归为同一键。 结果构造将哈希表中的每个值异位词组添加到结果向量中。
具体实现代码详解版):
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring mp; // 哈希表存储异位词组// 遍历每个字符串for (string str : strs) {string key str; // 复制当前字符串sort(key.begin(), key.end()); // 将字符串排序作为哈希表的键mp[key].push_back(str); // 将原字符串加入对应的组}vectorvectorstring ans; // 存储结果for (auto it mp.begin(); it ! mp.end(); it) {ans.push_back(it-second); // 将每组异位词添加到结果中}return ans; // 返回结果}
};
复杂度分析
时间复杂度O(nklogk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串对于每个字符串需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表因此总时间复杂度是 O(nklogk)。
3.128最长连续序列 思路分析1先排序虽然不符合 O ( n ) O(n) O(n)的时间复杂度吗但是是最快的
先对数组进行排序然后判断是否是连续序列 如果差1即是连续的数字更新最长序列长度 如果它们相等重复则可以忽略不需要修改 mx 否则说明当前数字与之前的连续序列断开了。需要重置当前序列长度 mx 为 1因为当前数字本身可以视为新的序列的开始。
具体实现代码详解版
class Solution {
public:int longestConsecutive(vectorint nums) {if(nums.size() 0) return 0; // 如果数组为空返回 0int ans 1, mx 1; // 初始化最长序列长度和当前序列长度sort(nums.begin(), nums.end()); // 对数组进行排序for(int i 1; i nums.size(); i) {if(nums[i - 1] 1 nums[i]) { // 如果是连续的数字ans max(ans, mx); // 更新最长序列长度}else if(nums[i - 1] nums[i]) { continue; // 跳过重复数字}else {mx 1; // 重置当前序列长度}}return ans; // 返回最长连续序列的长度}
};
2.思路分析2使用哈希集合优化为 O ( n ) O(n) O(n)) 使用 unordered_set 存储输入数组中的所有数字。这允许我们在 O(1) 的时间内快速查找任意数字。 通过 for 循环遍历 numSet 中的每个数字检查它是否是一个潜在的连续序列的起点。 确定起始点 通过 numSet.find(num - 1) numSet.end() 检查当前数字 num 是否是一个连续序列的起点。如果 num - 1 不在集合中说明 num 是一个新的序列的开始。 查找连续序列 如果 num 是起始数字初始化 currentNum 为 num并将 currentStreak 设为 1表示当前序列的长度。使用 while 循环查找 currentNum 1 是否存在于集合中。如果存在则 currentNum 自增并且 currentStreak 增加 1直到没有连续的数字为止。 更新最长序列长度在每次找到一个完整的连续序列后将 longestStreak 更新为当前序列长度和已有最长序列长度的较大值。 最后返回 longestStreak即数组中最长连续序列的长度
具体实现代码详解版
class Solution {
public:int longestConsecutive(vectorint nums) {// 使用 unordered_set 存储所有数字unordered_setint numSet(nums.begin(), nums.end());int longestStreak 0;// 遍历每个数字for (int num : numSet) {// 只从未处理的起始数字开始查找//如果 num - 1 不在集合中说明 num 是一个新的序列的开始。if (numSet.find(num - 1) numSet.end()) {int currentNum num;int currentStreak 1;// 向上查找连续的数字while (numSet.find(currentNum 1) ! numSet.end()) {currentNum;currentStreak;}// 更新最长序列长度longestStreak max(longestStreak, currentStreak);}}return longestStreak; // 返回最长连续序列的长度}
};这是两种算法的通过时间使用算法1的竟然还快一点~hhhh 总结哈希表集合常常用于解决与查找、计数或分组相关的问题在数据结构和算法中广泛应用如实现字典、集合等。哈希表是一种高效且灵活的数据结构适合于多种场景尤其是当需要快速查找、插入和删除时。理解其原理和使用方式可以帮助解决许多实际问题。
