287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
第一版，这个要求比较麻烦...，看的别人的,真的厉害
执行用时 :16 ms, 在所有 cpp 提交中击败了62.53%的用户
内存消耗 :10 MB, 在所有 cpp 提交中击败了12.18%的用户
intfindDuplicate(vector<int>&nums) {
intlen=nums.size();
intleft=0,counter=0;
intright=len-1;
while (left<right) {
intmid= (left+right+1) >>1;
for (int&num : nums) {
if (num<mid) {
counter++;
}
}
if (counter>=mid) {
right=mid-1;
}
else {
left=mid;
}
}
returnleft;
}
第二版，其实也是别人的法子，真的长见识了
(C++)二分法，主要原因是题目给出所有数都是1 - n，二分查找时的Mid就用来探测比Mid小的数有多少个。。。
classSolution
{
public:
intfindDuplicate(vector<int>&nums)
{
intlow=0, high=nums.size() -1;
while(low<high)
{
intmid=low+ ((high-low) >>2);
intcount=0;
for(intnum : nums)
if(num<=mid) count++;
if(count<=mid) low=mid+1;
elsehigh=mid;
}
returnlow;
}
};
792. 匹配子序列的单词数
给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:
- 所有在
words和S里的单词都只由小写字母组成。 S的长度在[1, 50000]。words的长度在[1, 5000]。words[i]的长度在[1, 50]。
第一版 emmmm...自己写的，很差
执行用时 :1136 ms, 在所有 cpp 提交中击败了5.05%的用户
内存消耗 :136 MB, 在所有 cpp 提交中击败了18.75%的用户
intnumMatchingSubseq(stringS, vector<string>&words) {
unordered_map<char, set<int>>mp;
for (unsignedi=0; i<S.size(); ++i) {
mp[S[i]].insert(i);
}
intcount=0,temp;
unsignedi=0;
for (auto&word : words) {
temp=*(mp[word[0]].begin());
for (i=1; i<word.size(); ++i) {
autopos=mp[word[i]].upper_bound(temp);
if (pos!=mp[word[i]].end()) {
if (*pos>temp) temp=*pos;
else
break;
}
else
break;
}
if (i==word.size()) count++;
}
returncount;
}
第二版，稍微改进一下
执行用时 :308 ms, 在所有 cpp 提交中击败了58.08%的用户
内存消耗 :40.5 MB, 在所有 cpp 提交中击败了65.63%的用户
intnumMatchingSubseq(stringS, vector<string>&words) {
unordered_map<char, vector<int>>mp;
for (unsignedi=0; i<S.size(); ++i) {
mp[S[i]].push_back(i);
}
intcount=0,temp;
unsignedi;
for (auto&word : words) {
if (mp.find(word[0]) ==mp.end()) //时刻注意判断问题
continue;
temp=*(mp[word[0]].begin());
for (i=1; i<word.size(); ++i) {
if (mp.find(word[i]) ==mp.end()) //时刻注意判断有无问题
break;
autopos=upper_bound(mp[word[i]].begin(), mp[word[i]].end(),temp);
if (pos!=mp[word[i]].end()) {
temp=*pos;
}
else
break;
}
if (i==word.size()) count++;
}
returncount;
}
378. 有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
说明:你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
第一版，优先队列做一次，用大顶堆求top小
intkthSmallest(vector<vector<int>>&matrix, intk) {
priority_queue<int,vector<int>,less<int>>result;
intlen=matrix[0].size();
intcount=0;
for (unsignedi=0; i<len; ++i) {
for (unsignedj=0; j<len; ++j) {
if (result.size() >=k) {
if(result.top()>matrix[i][j]){
result.push(matrix[i][j]);
result.pop();
}
}
else
result.push(matrix[i][j]);
}
}
returnresult.top();
}
执行用时 :48 ms, 在所有 cpp 提交中击败了67.71%的用户
内存消耗 :13.1 MB, 在所有 cpp 提交中击败了34.15%的用户
