九章 HIgh Frequency

九章 HIgh Frequency

1. Single Number I, II, III -> given an array of integers, every element appears twice except for two. find the two signles
2. Majority Number I, II, III
3. Best time to buy and sale stock I, II, III
4. Subarray I, II, III, IV
5. 2-Sum, 3-Sum, 4-Sum, k-Sum, 3-Sum Closest
6. Quick Questions

异或 xor
-不进位加法
-相同为0，不同为1

a^b=c
=> a^c = b
=> b ^ c = b

a^0 = a
a^a=0//抵消
a^(b^c) = (a^b)^c
c - c & (c-1) -> the low bit of c

Majority Number II
反例：1 0 3 10 4 1 1 2 2 2

Majority Number III
1. 保存k-1个数
2. O(1) 查询是否在这个集合中
3. O(1) count++
4. O(1) 插入
5. 对集合的所有数 count--

时间复杂度：看每个元素的操作次数-》每个元素进出数据结构几次

抵消的思路来实现O(1)的空间复杂度

Best Time to Buy and Sell Stock