365 day challenge leetcode 1000 questions - day 041 two point search completion anniversary + nth magic number + online election

Two point search completion Memorial

878. The first N A magic number

Code implementation （ Part depends on the solution ）

class Solution {
    
public:
    typedef long long ll;
    // greatest common divisor  greatest common divisor 
    ll gcd(ll a, ll b) {
    
        return b == 0 ? a : gcd(b, a % b);
    }
    // least common multiple  Minimum common multiple 
    ll lcm(ll a, ll b) {
    
        return a * b / gcd(a, b);
    }

    int nthMagicalNumber(int n, int a, int b) {
    
        ll ab = lcm(a, b);
        // The result of this question is  [1, 2 * 10^9]  Within the scope of , Optimize to  [min({a,b,c}), 2 * 10^9]
        ll l = min(a, b) - 1, r = 4e13 + 1; 
        while (l+1 != r) {
    
            ll mid = (l + r) >> 1;
            //  Principle of tolerance and exclusion ： Calculation  cnt  by [1,mid] Ugly number in 
            ll cnt = mid / a + mid / b - mid / ab;
            if (cnt < n) {
    
                l = mid;
            } else {
    
                r = mid;
            }
        }
        return r % 1000000007;
    }
};

---

911. Online elections

Code implementation （ Self solution ）

class TopVotedCandidate {
    
private:
    vector<int> times;
    map<int, int> query;
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) :
    times(times) {
    
        map<int, int> _map;
        int maxVotes = 0, selectedPerson = 0;
        for (int i = 0; i < times.size(); i++) {
    
            _map[persons[i]]++;
            for (auto it = _map.begin(); it != _map.end(); it++) {
    
                if (it->second > maxVotes) {
    
                    maxVotes = it->second;
                    selectedPerson = it->first;
                }
                
            }
            if (maxVotes == _map[persons[i]]) {
    
                selectedPerson = persons[i];
            }
            query[times[i]] = selectedPerson;
        }
    }
    
    int q(int t) {
    
        int l = 0, r = times.size() - 1, m = 0;
        while (l < r) {
    
            m = (l + r + 1) >> 1;
            if (times[m] <= t) l = m;
            else r = m - 1;
        }
        return query[times[l]];
    }
};

/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate* obj = new TopVotedCandidate(persons, times); * int param_1 = obj->q(t); */

---