初级算法（四）

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4

思路

  • 使用异或运算，将所有值进行异或
  • 异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
  • 因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算，单独的值就剩下了
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0;i<nums.size();i++){
            res ^=nums[i];
        }
        return res;
    }
};

效果

两个数组的交集 II

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

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：

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

思路

  1. 先对两个数组进行排序，然后使用两个指针，分别指向两个数组开始的位置。
  2. 如果两个指针指向的值相同，说明这个值是他们的交集，就把这个值加入到集合list中，然后两个指针在分别往后移一步。
  3. 如果两个指针指向的值不同，那么指向的值相对小的往后移一步，相对大的先不动，然后再比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
		sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
         int len1 = nums1.size();
         int len2 = nums2.size();
        //先对数组进行排序
        vector<int> list;//建立list
        int first=0,second=0;
        while(first<len1&&second<len2){
              if(nums1[first]==nums2[second])
                {
                    list.push_back(nums1[first]);
                    first++;
                    second++;
                }
            else if(nums1[first]>nums2[second]){
                    second++;
            } else{
                    first++;
                    }
        }
        return list;
    }
};

效果

坑爹的事

写完了代码，却一直无法AC。返回的list永远是空数组。我很纳闷，排查了一个小时左右。才是发现原来是给first和second的赋值问题。第一次写成int first,second=0;这种形式了。后来改成了int first=0,second=0;就通过了。他妈的！