class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
{
map<int,int> mp;
vector<int> ans;
for(auto i:nums1)
mp[i]+=1;
for(auto j:nums2)
{
if(mp[j]>0){
mp[j]-=1;
ans.push_back(j);
}
}
return ans;
}
};
如果给定数组已经排好序，优化版；
1，设定两个指针，比较两个指针指向元素，相同元素放进空白数组
2；不同元素，将指针指向小的元素后移
3，重复以上步骤，知道任意一个数组终止
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
{
int i=0,j=0,k;
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
vector<int> ans;
while(i<nums1.size() && j<nums2.size() )
{
if(nums1[i]>nums2[j])
j++;
else if(nums1[i]<nums2[j])
i++;
else
{
ans.push_back(nums2[j]);
i++;
j++;
}
}
return ans;
}
};
...一定要初始化......
遍历过后的数组没用，可以用来储存答案，节省内存和空间；
第二种比第一种内存小；
最长公共前缀-lc14
找字符串数组中的最长公共前缀；
解：将第一个元素作为基准元素，依次将基准元素与后边的每个元素相比较，不断更新基准元素，直到基准元素和所有元素都满足公共前缀
如果基准元素和任意一个元素无法匹配，不存在公共前缀，直接退出。
特判一下数组为空的情况。
compare(X0,x);(X0为基准元素，x为比较元素)；
如果conpare（x0，x）==0，截取掉x0的最后一个元素，依次比较直到得出结果
比如flight和flow
flight ----flow 去掉t，h，g，i之后，前缀为fl
代码：
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length<1)
return "";
int idx=0;
for(int i=0; i<strs[0].length(); i++)
{
char cur=strs[0].charAt(i);//charAt返回指定索引时的值
for(String str :strs)
{
if(str.length()==i||cur!=str.charAt(i))
return str.substring(0,idx);
}
idx++;
}
return strs[0].substring(0,idx);
}
}
class Solution{
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
{//Java的indexof函数直接在一个字符串中找另一个字符串
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}
}