数组和集合的搜索
目录
一，数组和集合的搜索
DFS、BFS一般用来解决树和图的搜索问题，对象空间是不是良序的，
而数组和集合的搜索，对象空间是良序的。
DFS、BFS一般把对象空间搜索一遍就能得到答案，比较复杂的问题往往复杂度在于如何高效剪枝，
而数组和集合的搜索，往往搜索一遍还得不到答案，
比如寻找2个数的和为给定数的所有数对，需要两层的嵌套搜索，暴力时间是O(n^2)，
一些技巧，比如二分等，可以用在数组和集合的搜索问题上，但不能用于DFS、BFS
二，OJ实战
力扣 1. 两数之和（二分法）
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路：枚举一个数，嵌套搜索另外一个数的时候采用二分法
-
//给vector拓展，加上id并排序
-
template<typename T>
-
bool cmp(T x,T y)
-
{
-
return x<y;
-
}
-
template<typename T>
-
vector<pair<T,int>> sortWithId(vector<T>v)
-
{
-
vector<pair<T,int>>ans;
-
ans.resize(v.size());
-
for(int i=0;i<v.size();i++)ans[i].first=v[i],ans[i].second=i;
-
sort(ans.begin(),ans.end(),[](pair<T,int>p1,pair<T,int>p2){return cmp(p1.first,p2.first);});
-
return ans;
-
}
-
//2个vector中寻找和为s的对，返回结果的每一行都是[id1,id2]
-
template<typename T>
-
vector<vector<int>> findSum(vector<T>v1,vector<T>v2,T s)
-
{
-
vector<vector<int>>ans;
-
vector<int>tmp(2);
-
vector<pair<T,int>>v3=sortWithId(v2);
-
sort(v2.begin(), v2.end(),cmp<T>);
-
for(int i=0;i<v1.size();i++)
-
{
-
auto it1=lower_bound(v2.begin(), v2.end(), s-v1[i]);
-
auto it2=upper_bound(v2.begin(), v2.end(), s-v1[i]);
-
tmp[0]=i;
-
for(auto j=it1;j<it2;j++)
-
{
-
tmp[1]=v3[j-v2.begin()].second;
-
ans.push_back(tmp);
-
}
-
}
-
return ans;
-
}
-
//删除二维vector中，含有重复元素的行
-
template<typename T>
-
vector<vector<T>> deleteSame(vector<vector<T>>&v)
-
{
-
vector<vector<int>>ans;
-
ans.reserve(v.size());
-
for(int i=0;i<v.size();i++)
-
{
-
for(int j=0;j<v[i].size();j++)for(int k=j+1;k<v[i].size();k++)if(v[i][j]==v[i][k])goto here;
-
ans.push_back(v[i]);
-
here:;
-
}
-
return ans;
-
}
-
class Solution {
-
public:
-
vector<int> twoSum(vector<int>& nums, int target) {
-
vector<vector<int>>ans=findSum(nums,nums,target);
-
return deleteSame(ans)[0];
-
}
-
};
力扣 167. 两数之和 II - 输入有序数组（二分法）
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
题目和 力扣OJ 1. 两数之和 基本没啥差别。
-
//vector加一个数
-
template<typename T1,typename T2>
-
void fjia(vector<T1> &v,T2 n)
-
{
-
for(int i=v.size()-1;i>=0;i--)v[i]+=n;
-
}
-
class Solution {
-
public:
-
vector<int> twoSum(vector<int>& nums, int target) {
-
vector<vector<int>>ans=findSum(nums,nums,target);
-
vector<int>res = deleteSame(ans)[0];
-
fjia(res,1);
-
return res;
-
}
-
};
PS：省略重复代码
力扣 454. 四数相加 II（二分+计重）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
-
//给vector拓展，加上id并排序
-
template<typename T>
-
bool cmp(T x,T y)
-
{
-
return x<y;
-
}
-
template<typename T>
-
vector<pair<T,int>> sortWithId(vector<T>v)
-
{
-
vector<pair<T,int>>ans;
-
ans.resize(v.size());
-
for(int i=0;i<v.size();i++)ans[i].first=v[i],ans[i].second=i;
-
sort(ans.begin(),ans.end(),[](pair<T,int>p1,pair<T,int>p2){return cmp(p1.first,p2.first);});
-
return ans;
-
}
-
//2个vector中寻找和为s的对，返回结果的每一行都是[id1,id2]
-
template<typename T>
-
vector<vector<int>> findSum(vector<T>v1,vector<T>v2,T s)
-
{
-
vector<vector<int>>ans;
-
int m=min((long long)(v1.size()*v2.size()),(long long)12345678);
-
ans.reserve(m);
-
vector<int>tmp(2);
-
vector<pair<T,int>>v3=sortWithId(v2);
-
sort(v2.begin(), v2.end(),cmp<T>);
-
for(int i=0;i<v1.size();i++)
-
{
-
auto it1=lower_bound(v2.begin(), v2.end(), s-v1[i]);
-
auto it2=upper_bound(v2.begin(), v2.end(), s-v1[i]);
-
tmp[0]=i;
-
for(auto j=it1;j<it2;j++)
-
{
-
tmp[1]=v3[j-v2.begin()].second;
-
ans.push_back(tmp);
-
}
-
}
-
return ans;
-
}
-
//枚举2个vector的两数之和
-
template<typename T>
-
vector<T> everySum(vector<T>&v1,vector<T>&v2)
-
{
-
vector<T>ans;
-
ans.resize(v1.size()*v2.size());
-
int k=0;
-
for(int i=0;i<v1.size();i++)for(int j=0;j<v2.size();j++)ans[k++]=v1[i]+v2[j];
-
return ans;
-
}
-
//判断有序数组中有多少个不同的数
-
template<typename T>
-
int getDifNum(vector<T>v)
-
{
-
int ans=1;
-
for(int i=1;i<v.size();i++)ans+=(v[i]!=v[i-1]);
-
return ans;
-
}
-
//收缩计数,把[1 1 4 4 4]变成[(1,2)(4,3)]
-
template<typename T>
-
vector<pair<T,int>> fshr(vector<T>v)
-
{
-
vector<pair<T,int>>ans;
-
if(v.size()==0)return ans;
-
sort(v.begin(),v.end());
-
ans.resize(getDifNum(v));
-
ans[0]=make_pair(v[0],1);
-
for(int i=1,j=0;i<v.size();i++)
-
{
-
if(v[i]==v[i-1])ans[j].second++;
-
else ans[++j]=make_pair(v[i],1);
-
}
-
return ans;
-
}
-
//提取pair数组的first
-
template<typename T1,typename T2>
-
vector<T1> fdraw(vector<pair<T1,T2>>v)
-
{
-
vector<T1>ans(v.size());
-
for(int i=0;i<v.size();i++)ans[i]=v[i].first;
-
return ans;
-
}
-
//提取pair数组的second
-
template<typename T1,typename T2>
-
vector<T2> fdraw2(vector<pair<T1,T2>>v)
-
{
-
vector<T2>ans(v.size());
-
for(int i=0;i<v.size();i++)ans[i]=v[i].second;
-
return ans;
-
}
-
class Solution {
-
public:
-
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
-
vector<int> v1 = everySum(A,B),v2 = everySum(C,D);
-
vector<pair<int,int>>v3=fshr(v1),v4=fshr(v2);
-
vector<int> v5=fdraw(v3),v6=fdraw(v4);
-
vector<int> v7=fdraw2(v3),v8=fdraw2(v4);
-
vector<vector<int>> ans = findSum(v5,v6,0);
-
int res=0;
-
for(int i=0;i<ans.size();i++)res+=v7[ans[i][0]]*v8[ans[i][1]];
-
return res;
-
}
-
};
力扣 136. 只出现一次的数字（基于计算的搜索）
题目：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
代码：
-
class Solution {
-
public:
-
int singleNumber(vector<int>& nums) {
-
int ans = 0;
-
for (auto it = nums.begin(); it != nums.end(); it++)ans ^= *it;
-
return ans;
-
}
-
};
力扣 137. 只出现一次的数字 II（基于计算的搜索）
题目：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
代码：
-
class Solution {
-
public:
-
long long yiHuoAtBase3(long long a, long long b)
-
{
-
for (long long k = 1; k <= b; k *= 3){
-
a -= (a / k % 3 - (a / k + b / k) % 3)*k;
-
}
-
return a;
-
}
-
int singleNumber(vector<int>& nums) {
-
long long ans1 = 0, ans2 = 0;
-
for (auto it = nums.begin(); it != nums.end(); it++){
-
long long tem = *it;
-
if (tem >= 0){
-
ans1 = yiHuoAtBase3(ans1, tem);
-
}
-
else{
-
ans2 = yiHuoAtBase3(ans2, -tem);
-
}
-
}
-
return ans1-ans2;
-
}
-
};
力扣 260. 只出现一次的数字 III（基于计算的搜索）
题目：
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
代码：
-
class Solution {
-
public:
-
vector<int> singleNumber(vector<int>& nums) {
-
int k, s, s1, s2;
-
s = 0;
-
for (int i = 0; i < nums.size(); i++)s ^= nums[i];
-
s = s & -s;
-
s1 = 0, s2 = 0;
-
for (int i = 0; i < nums.size(); i++)
-
{
-
if (s&nums[i])s1 ^= nums[i];
-
else s2 ^= nums[i];
-
}
-
vector<int>ans;
-
ans.insert(ans.end(), s1);
-
ans.insert(ans.end(), s2);
-
return ans;
-
}
-
};
力扣 268. 缺失数字（基于计算的搜索）
题目：
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
代码：
-
class Solution {
-
public:
-
int missingNumber(vector<int>& nums) {
-
int n = nums.size();
-
int ans = 0;
-
for (int i = 1; i <= n; i++)ans ^= (i^nums[i - 1]);
-
return ans;
-
}
-
};
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/116016266
- 点赞
- 收藏
- 关注作者
评论（0）