# 350, 217, 136-Duplicates in Arrays

###### tags: `Easy`、`Array`

# **350-Intersection of Two Arrays II**
## Question


https://leetcode.com/problems/intersection-of-two-arrays-ii/

## Solution
- 想法:先將比較小的陣列元素和其發生次數都存到hash table，再清空比較小的那個陣列，就能拿來存重複的元素作為答案，不用再另外創新的空間，接著較大的陣列中的元素逐一搜尋是否在table中，有的話，就扣掉一個，如果扣完等於0就將該元素從table中移除，直到陣列遍尋完或table空了
### C++ Sol.

class Solution {
public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    if(nums1.size() > nums2.size()) 
    {
        swap(nums1, nums2); 
    }
    unordered_map<int,int> table;
    for(auto &x: nums1) table[x]++;
    nums1.clear();
    
    for(int i = 0; i != nums2.size() && !table.empty(); i++)
      if(table.count(nums2[i]))
      {
        if(--table[nums2[i]] == 0)
        {
            table.erase(nums2[i]);
        }

        nums1.push_back(nums2[i]);
      }
    
    return nums1; 
  }
};

### Python Sol.

class Solution(object):
    def intersect(self, nums1, nums2):
        occurences = {} #dictionary
        intersection = [] #list
        for num in nums1:
            occurences[num]=0
        for num in nums1:
            occurences[num]+=1
        for num in nums2:
            if num in occurences and occurences[num]>0:
                intersection.append(num)
                occurences[num]-=1
        return intersection  

# **217-Contains Duplicate**
## Question
https://leetcode.com/problems/contains-duplicate/

## Solution

class Solution:
    def containsDuplicate(self, nums):
        dt = dict()
        for num in nums:
            if dt.get(num):
                return True
            dt[num] = 1
        return False 

# **136-Single number**
## Question

**with a linear runtime complexity and use only constant extra space** -> hash table space O(N)不行 ->XOR

>A^A=0
A^B^A=B
(A^A^B) = (B^A^A) = (A^B^A) = B This shows that position doesn't matter.
Similarly , if we see , a^a^a......... (even times)=0 and a^a^a........(odd times)=a

## Solution
### C++

class Solution {
public:
    int singleNumber(vector<int>& nums) { 
       int ans=0;
	   for(auto x:nums)
	   ans^=x;
	   return ans;
    }
};

### Faster solution with range for(auto for loop)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        auto x = 0;
        for(auto &i: nums) {
            x ^= i;
        }
        return x;
    }
};

### 補充:
1. 在 C++11 標準下，對於有被明確初始化的變數，我們可以使用 auto 這個新的變數類型，讓編譯器自動判斷其變數的類型
2. C++14 之後，函數的傳回值也可以使用 auto
3. range-for 可能比 iteration-for來的快一點點
https://stackoverflow.com/questions/10821756/is-the-ranged-based-for-loop-beneficial-to-performance

### python

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        
        for i in range(1, len(nums)):
            res ^= nums[i]
        return res

TC: O(N)
SC: O(1)

python 運算子補充:
https://ithelp.ithome.com.tw/articles/10211263