STL 容器类型的OJ题篇1

淡淡的烟草味﹌ 2023-06-24 08:13 14阅读 0赞

### STL 容器解题 ###

*   *   *  1、数组中的第 K 个最大元素
         *  2、前 K 个高频元素
         *  3、重复 N 次的元素
         *  4、两个数组的交集
         *  5、两个数组的交集 II
         *  6、 两句话中的不常见单词
         *  7、 有序矩阵中第 K 小的元素
         *  8、根据字符出现的频率排序

### 1、数组中的第 K 个最大元素 ###

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

> 示例 1:  
> 输入: \[3,2,1,5,6,4\] 和 k = 2  
> 输出: 5

> 示例 2:  
> 输入: \[3,2,3,1,2,4,5,5,6\] 和 k = 4  
> 输出: 4

**方法一**：定义一个优先级队列，因为它的底层是大顶堆，然后弹出 k-1个元素，顶元素就是第 k 个大的 元素

int findKthLargest(vector<int>& nums, int k) { 
    	priority_queue<int>p(nums.begin(),nums.end());
    	for(int i = 0;i<k-1;++i){ 
    		p.pop();
    	}   
        return p.top();
    }

**方法二**： 利用排序库函数

sort(nums.begin(),nums.end());
    return nums[nums.size()-k];

lambda 表达式定义一个降序排序

int findKthLargest(vector<int>& nums, int k) { 
    	sort(nums.begin(),nums.end(),[](int a,int b){ 
        	return a>b;
    	});
    	return nums[k-1];
    }

python 函数可以直接利用排序的库函数

# 库函数1 
    num = sorted(num,reverse=True);
    # 库函数2 
    # nums.sort(reverse=True)
    return num[k-1]

### 2、前 K 个高频元素 ###

给定一个非空的整数数组，返回其中出现频率前 k 高的元素

> 示例 1:  
> 输入: nums = \[1,1,1,2,2,3\], k = 2  
> 输出: \[1,2\]

> 示例 2:  
> 输入: nums = \[1\], k = 1  
> 输出: \[1\]

说明：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数

**你的算法的时间复杂度必须优于 O(n\*logn) , n 是数组的大小**

方法一：C++ 版本

思路：先将数据本身和次数统一，放到一个 unordered\_map 序列式容器中，然后把 pair<key,value> 作为一个元素插入到优先级队列中

vector<int> topKFrequent(vector<int>& nums, int k) { 
            priority_queue<pair<int,int>>p;
            vector<int>res;
            unordered_map<int,int>mp;
            for(auto&e: nums){ 
                mp[e]++;
            }
            // 将数据导入到优先级队列中
            for(auto&e: mp){ 
            	// 元素的次数作为键，元素本身的内容作为值
                p.push(pair<int,int>(e.second,e.first));
            }
            // 删除堆第一个元素，因为第一个元素就是最大值
            // 删除完之后再进行调整，将次大的值调整到堆顶
            while(k--){ 
                res.push_back(p.top().second);
                p.pop();
            }
            return res;
        }

方法二：python 版本

思路：把所有的元素组合到字典中，然后按照键值从大到小排序，键值就是某一个元素出现的次数，最后返回前 k 个元素

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
            res = []
            dic = { }
            for i in range(len(nums)):
                if nums[i] not in dic:
                    dic[nums[i]] = 1
                else:
                    dic[nums[i]]+=1
     		# items 函数以列表返回可遍历的(键, 值) 元组数组
     		# 根据它的第二个值进行降序排序
            dic = sorted(dic.items(),key=lambda x:x[1],reverse=True)
            for key,_ in dic[:k]:
                res.append(key)
            return res

### 3、重复 N 次的元素 ###

在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次

返回重复了 N 次的那个元素

> 示例 1：  
> 输入：\[1,2,3,3\]  
> 输出：3

> 示例 2：  
> 输入：\[2,1,2,5,3,2\]  
> 输出：2

> 示例 3：  
> 输入：\[5,1,5,2,5,3,5,4\]  
> 输出：5

提示：  
4 <= A.length <= 10000  
0 <= A\[i\] < 10000  
A.length 为偶数

**思路**：利用 unordered\_map 结构，底层是通过哈希表来实现的，所以我们访问的时候可以以O（1）的时间快速查找

int repeatedNTimes(vector<int>& A) { 
            size_t N = A.size()/2;
            // 用unordered_map统计每个元素出现的次数
            unordered_map<int, int> m;
            for(auto e : A)
                m[e]++;
            // 找出出现次数为N的元素
            for(auto& e : m){ 
                if(e.second == N)
                return e.first;
            }
            return 0;
        }

用 python 也是非常简单的，直接用一个字典结构就可以了

### 4、两个数组的交集 ###

给定两个数组，编写一个函数来计算它们的交集

> 示例 1:  
> 输入: nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
> 输出: \[2\]

> 示例 2:  
> 输入: nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
> 输出: \[9,4\]

说明:

输出结果中的每个元素一定是唯一的。  
我们可以不考虑输出结果的顺序

方法一 ：python 版本

在遍历 nums1 的时候，查看当前元素是否在 num2 中，如果在则插入到一个列表 ，然后利用 set 函数去重

def intersection(nums1, nums2):
            res = []
            for i in nums1:
                if i in nums2:
                    res.append(i)
            return set(res)

方法二：C++ 版本

思路基本和 python 一致，把数据放到一个 unordered\_set 关联式容器中，通过遍历 nums 1 或者 nums2 来判断是否有重叠元素

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 
            // 首先给 num1 和 nums2 去重
            unordered_set<int>us1;
            for(auto&e:nums1){ 
                us1.insert(e);
            }
            unordered_set<int>us2;
            for(auto&e:nums2){ 
                us2.insert(e);
            }
            // 如果 us1 中的元素在 us2中，那么则插入到返回数组中
            vector<int>res;
            for(auto&e:us1){ 
                if(us2.find(e)!=us2.end()){ 
                    res.push_back(e);
                }
            }
            return res;
        }

### 5、两个数组的交集 II ###

给定两个数组，编写一个函数来计算它们的交集。

> 示例 1:  
> 输入: nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
> 输出: \[2,2\]

> 示例 2:  
> 输入: nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
> 输出: \[4,9\]  
> 说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致(不考虑输出结果的顺序)

进阶:  
如果给定的数组已经排好序呢？你将如何优化你的算法？  
如果 nums1 的大小比 nums2 小很多，哪种方法更优？  
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

方法一：在 python 中有一个 & 符号可以在集合中计算交集，然后利用 count 函数计数该字符出现的次数

def intersect(nums1, nums2):
            # 转换为集合，然后求出交集
            inter = set(nums1) & set(nums2)
            res = []
            for i in inter:
                res += [i] * min(nums1.count(i), nums2.count(i))  
            return res

方法二：在 num2 中找到一次就删除一次，这样就不用计算次数了

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
            n=len(nums1)
            nums=[]
            for i in range(n):
                if nums1[i] in nums2:
                    nums.append(nums1[i])
                    nums2.remove(nums1[i])
            return nums

方法三：C++ 思路，利用 unordered\_map 容器

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { 
            unordered_map<int,int> dict;
            vector<int> res;
            for(auto i : nums1)
                dict[i]++;
            
            for(auto j : nums2){ 
                if(dict.count(j)){ 
                    res.push_back(j);
                    dict[j]--;
                    // 当 dict[j]==0意味着没有元素了
                    // 但是 count 值还会返回1，所以需要删除掉
                    if(dict[j] == 0)
                        dict.erase(j);
                }
            }
            return res;
        }

### 6、 两句话中的不常见单词 ###

给定两个句子 A 和 B (句子是一串由空格分隔的单词。每个单词仅由小写字母组成)

如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的

返回所有不常用单词的列表，您可以按任何顺序返回列表

> 示例 1：  
> 输入：A = “this apple is sweet”, B = “this apple is sour”  
> 输出：\[“sweet”,“sour”\]

> 示例 2：  
> 输入：A = “apple apple”, B = “banana”  
> 输出：\[“banana”\]

提示：

0 <= A.length <= 200  
0 <= B.length <= 200  
A 和 B 都只包含空格和小写字母

方法一：输入流和输出流

根据题目意思我们不难发现，需要返回两个句子中只出现一次的单词，所以我们先把两个句子合并为一句然后转换为列表，通过字典遍历如果 value 等于 1，则把对应的 key 添加到返回列表中

vector<string> uncommonFromSentences(string A, string B) { 
            string str = A + " " + B;
            unordered_map<string,int>mp;
            string temp;
            stringstream stream(str);   
            while(stream>>temp){ 
                mp[temp]++;
            }
            vector<string>res;
            for(auto i = mp.begin();i!=mp.end();++i){ 
                if(i->second ==1){ 
                    res.push_back(i->first);
                }  
            }
            return res;
        }

方法二：python 版本写起来比较简单

def uncommonFromSentences(self, A: str, B: str) -> List[str]:
            dic = { }
            temp = A.split() + B.split()
            for s in temp:
                if s not in dic:
                    dic[s]=1
                else:
                    dic[s]+=1
            res = []
            for key,value in dic.items():
                if value == 1:
                    res.append(key)
            return res

### 7、 有序矩阵中第 K 小的元素 ###

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素

**注意，它是排序后的第 k 小元素，而不是第 k 个元素**

> 示例  
> matrix = \[  
> \[ 1, 5, 9\],  
> \[10, 11, 13\],  
> \[12, 13, 15\]  
> \]  
> k = 8  
> 返回 13

方法一：将所有数放到一个列表中，然后对列表进行排序，最后取出第k个元素

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
            res = []
            #for num in matrix:
            # res += num
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    res.append(matrix[i][j])
            res.sort()
            return res[k-1]

方法二：可以将数据放入一个优先级队列，然后弹出 size-k 个元素，返回队列的首元素，当然这种方法和第一种差不多

int kthSmallest(vector<vector<int>>& matrix, int k) { 
            priority_queue<int>pq;
            for(int i = 0;i<matrix.size();++i){ 
                for(int j = 0;j<matrix[0].size();++j){ 
                    pq.push(matrix[i][j]);
                }
            }
            int row = matrix.size();
            int col = matrix[0].size();
            int n = row*col-k;
            while(n--){ 
                pq.pop();
            }
            return pq.top();
        }

方法三：二分查找

1.找出二维矩阵中最小的数 min，最大的数 max，那么第k小的数必定在left~right之间

2.mid=(min+max) / 2；在二维矩阵中寻找小于等于 mid 的元素个数count

3.若这个 count 小于 k ，表明第 k 小的数在右半部分且不包含mid，即 min=mid+1, 又保证了第k小的数在 min ~ max之间

4.若这个 count 大于 k，表明第 k 小的数在左半部分且可能包含 mid，即 max=mid，又保证了第k小的数在 min ~ max 之间

5.因为每次循环中都保证了第 k 小的数在 min ~ max 之间，当 min == max 时，第 k 小的数即被找出，等于 min

int find(vector<vector<int>>& matrix,int mid){ 
            int count = 0;
            for(int i = 0;i<matrix.size();++i){ 
                for(int j = 0;j<matrix[0].size();++j){ 
                    if(matrix[i][j]<=mid){ 
                        ++count;
                    }
                }
            }
            return count;
        }
        int kthSmallest(vector<vector<int>>& matrix, int k) { 
            int row = matrix.size();
            int col = matrix[0].size();
            int min = matrix[0][0];
            int max = matrix[row-1][col-1];
            while(min < max){ 
                int mid = min+(max-min)/2;
                int count = find(matrix,mid);
                if(count<k){ 
                    min =mid+1;
                }else{ 
                    max = mid;
                }
            }
            return min;
        }

### 8、根据字符出现的频率排序 ###

给定一个字符串，请将字符串里的字符按照出现的频率降序排列

> 示例1  
> 输入:  
> “tree”  
> 输出:  
> “eert”  
> 解释:  
> 'e’出现两次，'r’和’t’都只出现一次。  
> 因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。

> 示例2  
> 输入:  
> “cccaaa”  
> 输出:  
> “cccaaa”  
> 解释:  
> 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。  
> 注意"cacaca"是不正确的，因为相同的字母必须放在一起。

> 示例3  
> 输入:  
> “Aabb”  
> 输出:  
> "bbAa  
> 解释:  
> 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。  
> 注意’A’和’a’被认为是两种不同的字符

思路：首先对字符串s中的元素进行计数，然后根据 key 进行降序排列，但是在排列的过程中去掉了重复值，所以后面在重组字符串的时候，需要对字符出现的个数乘以字符.

from collections import Counter
    def frequencySort(self, s: str) -> str:
    	d = Counter(s)
       	# 对key 进行降序的排列
        res = sorted(d,key=d.get,reverse=True)
        return ''.join([x*d[x] for x in res])

C++版本:利用 multimap 和 map 关联式容器，首先利用 map 对字符串进行计数和排序，然后在将数据导入到 multimap 容器中，进行输出

之所以不直接使用 multimap 容器，是因为 multimap 不支持下标访问，也没有库函数将数据直接写入到multimap中，

当数据导入到multimap 中，该容器会自动根据key值进行升序排序，key的类型是int，这正好满足题目要求

最后注意的一点是：如果是从前往后遍历 multimap容器的元素，就需要倒插入或者倒覆盖，如果是从后往前遍历，直接进行字符串的尾加操作就可以了

class Solution { 
    public:
        string frequencySort(string s) { 
            for(auto&e : s){ 
                mp[e]++;
            }
            for(auto p=mp.begin();p!=mp.end();p++){ 
                multi.insert(make_pair(p->second,p->first));
            }
            int n = s.size()-1;
            for(auto p=multi.begin();p!=multi.end();p++){ 
                int a = p->first;
                char c = p->second;
                // 这里采用的是覆盖，也可以另外定义一个字符串变量返回
                while(a-- >0){ 
                    s[n--] = c;
                }
            }
            return s;
        }
    private:
    	map<char,int>mp;
        multimap<int,char>multi;
    };