这两道题都是求两个数组之间的重复元素，因此把它们放在一起。
原题地址：
349 Intersection of Two Arrays ：https://leetcode.com/problems/intersection-of-two-arrays/description/
350 Intersection of Two Arrays II：https://leetcode.com/problems/intersection-of-two-arrays-ii/description/
题目&&解法：
1.Intersection of Two Arrays：
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
这道题目要注意的就是不能重复。我采取的做法是遍历一遍nums1数组，然后和nums2数组比对，假如nums2里面存在并且要返回的数组中没有这个数值，就把他插入要返回的数组里面。很低端的一种做法，代码如下：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> temp;
for (int i = ; i < nums1.size(); i++) {
if (find(nums2.begin(), nums2.end(), nums1[i]) != nums2.end() && find(temp.begin(), temp.end(), nums1[i]) == temp.end()) {
temp.push_back(nums1[i]);
}
}
return temp;
}
};
2.Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
这道题目比上面的题目复杂了一点，它要求把重复的元素都放进返回的数组里面，我采取了一种非常非常垃圾的做法：先定义一个结构体，一个int类型和一个bool类型，int变量数值复制传入的数组，然后用bool变量标记当前元素的数值是否已经插入要返回的数组。然后采取双层循环逐个比对。代码如下：
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
struct v{
int data;
bool isChoosed;
};
vector<struct v> struct_num1;
vector<struct v> struct_num2;
for (int i = ; i < nums1.size(); i++) {
struct v t;
t.data = nums1[i];
t.isChoosed = false;
struct_num1.push_back(t);
}
for (int i = ; i < nums2.size(); i++) {
struct v t;
t.data = nums2[i];
t.isChoosed = false;
struct_num2.push_back(t);
}
vector<int> temp;
for (int i = ; i < nums1.size(); i++) {
for (int j = ; j < nums2.size(); j++) {
if (struct_num1[i].data == struct_num2[j].data && struct_num2[j].isChoosed == false && struct_num1[i].isChoosed == false) {
temp.push_back(struct_num2[j].data);
struct_num1[i].isChoosed = true;
struct_num2[j].isChoosed = true;
}
}
}
return temp;
}
};
这种做法让我鄙视我自己，时间复杂度为O(n^2)，极高。而且写起来极其麻烦。肯定有简单的方法啊！
根据http://blog.csdn.net/yzhang6_10/article/details/51526070里面的一种比较快的思路：
（1）先对两个数组进行排序
（2）遍历两个数组，比较对应元素：若相等，两个数组的索引同时增加；若不等，较小元素的数组的索引增加。
这是一个极精妙的方法，个人感觉原理和归并数组有点相似。这个算法值得经常去回顾一下，特此记录。
代码如下：
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> result;
for (int i = , j = ; i < nums1.size() && j < nums2.size(); )
{
if (nums1[i] == nums2[j])
{
result.push_back(nums1[i]);
i++;
j++;
}
else if (nums1[i] < nums2[j])
i++;
else if (nums1[i] > nums2[j])
j++;
}
return result;
}
};