leetcode补全计划-20180810

1. 220 Contains Duplicate III
   输入：vector<int>& nums, int k, int t
   输出：bool
   要求：该数组中是否有两个数num[i]和num[j]符合下面的两个要求：|nums[i] - nums[j]| <= t && |i - j| <= k
   思路：|nums[i] - nums[j]| <= t可以转化成nums[i] >= nums[j] - t && nums[i] <= nums[j] + t,故可以使用set的lower_bound来实现第一个条件，得到相应的nums[i],如果这个数字能够实现第二个条件，那么返回true

typedef long long LL;
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(k <= 0 || t < 0) return false;
        set<LL> order;
        for(int i = 0;i < nums.size();++ i){
            auto it = order.lower_bound((LL)nums[i] - (LL)t);
            if(it != order.end() && *it <= ((LL)nums[i] + (LL)t))
                return true;
            if(i >= k) order.erase(nums[i - k]);
            order.insert(nums[i]);
        }
        return false;
    }
};

2. 229 Majority Element II
   输入：vector<int>
   输出：vector<int>
   要求：求nums中出现概率超过1/3的数字。
   思路：先找到出现次数最多的1-2个数字，之后再数个数。
   之所以能够数出来，是因为假如数字a出现的概率超过1/3，则+1的次数要多于-1的次数。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ret;
        int size = nums.size();
        if(size == 0) return ret;
        if(size == 1){
            ret.push_back(nums[0]);
            return ret;
        }
        int n1 = nums[0];
        int n2 = 0;
        int c1 = 1;
        int c2 = 0;
        for(int i = 0;i < size;++ i){
            if(c1 == 0) n1 = nums[i];
            else if(c2 == 0) n2 = nums[i];
            if(nums[i] == n1){
                c1 ++;
            }else if(nums[i] == n2){
                c2 ++;
            }else{
                c1 --;
                c2 --;
            }
        }
        c1 = c2 = 0;
        for(auto a : nums){
            if(a == n1) c1 ++;
            if(a == n2) c2 ++;
        }
        if(c1 * 3 > size) ret.push_back(n1);
        if(c2 * 3 > size && n1 != n2) ret.push_back(n2);
        return ret;
    }
};