Algorithms & Data Structures : Binary Search Problems

Problem

LeetCode 528. Random Pick with Weight

LeetCode : 1901. Find a Peak Element II
[binary search][matrix]

LeetCode : 2064. Minimized Maximum of Products Distributed to Any Store
[binary search][array]

LeetCode : 731. My Calendar II
[binary search][red-black tree][segment tree]

LeetCode : 2389. Longest Subsequence With Limited Sum
[Binary Search][Sorting][Greedy][Prefix Sum][Array]

LeetCode : 2485. Find the Pivot Integer
[Binary Search]

—

LeetCode 4. Median of Two Sorted Arrays

LeetCode 528. Random Pick with Weight

首先求前綴和，並且取總和範圍內的隨機數。
最後二分搜看該數在哪個區間內。

class Solution {
private:
    vector<int> prefixSum;
    int sum = 0;
public:
    Solution(vector<int>& w) {
        prefixSum = vector<int>(w.size(), 0);
        for(int i = 0;i < w.size();i++) {
            sum += w[i];
            prefixSum[i] = sum;
        }
    }
    
    int pickIndex() {
        int tmp = rand() % sum + 1;
        
        int left = 0;
        int right = prefixSum.size() - 1;
        int mid;
        int res = -1;
        while(left <= right) {
            mid = (left + right) / 2;
            if(prefixSum[mid] >= tmp) {
                if(-1 == res) {
                    res = mid;
                } else {
                    res = min(res, mid);
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return res;
    }
};

LeetCode : 1901. Find a Peak Element II

// TODO : 沒看到複雜度限制 QQ 
// 想一下要怎麼降複雜度
class Solution {
public:
    
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        for(int i = 0;i < mat.size();i++) {
            for(int j = 0;j < mat[0].size();j++) {
                
                bool f = true;
                for(int q = 0;q < 4;q++) {
                    int newx = i + X[q];
                    int newy = j + Y[q];
                    
                    if(newx >= 0 && newx < mat.size() &&
                       newy >= 0 && newy < mat[0].size()) {
                        if(mat[newx][newy] > mat[i][j]) {
                            f = false;
                            break;
                        }
                    }
                }
                if(f) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
};

LeetCode : 2064. Minimized Maximum of Products Distributed to Any Store

// binary search
// TODO : 太慢了
#define LL long long
class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        
        LL left = 0;
        LL right = INT_MAX;
        LL minVal = INT_MAX;
        
        while(left <= right) {
            LL mid = (left + right) / 2;
            
            if(0 == mid) {
                left = mid + 1;
                continue;
            }
            
            //printf("mid : %d\n", mid);
            
            LL tmp = 0;
            for(int i = 0;i < quantities.size();i++) {
                tmp += (quantities[i] / mid);
                if(0 != quantities[i] % mid) {
                    tmp++;
                }
            }
            if(tmp > n) {
                left = mid + 1;
            } else {
                minVal = min(minVal, mid);
                right = mid - 1;
            }
        }
        
        return minVal;
    }
};

LeetCode : 731. My Calendar II

// TODO : 時間空間效能太差
class MyCalendarTwo {
private:    
    // map<distance, v[type] : num
    // type == 0 : start
    // type == 1 : end
    map<int, vector<int>> m;
public:
    MyCalendarTwo() {
        
    }
    
    bool book(int start, int end) {
        if(m.find(start) == m.end()) {
            m[start] = vector<int>(2, 0);
        }
        m[start][0]++;
        
        if(m.find(end) == m.end()) {
            m[end] = vector<int>(2, 0);
        }
        m[end][1]++;
        
        int num = 0;
        bool f = true;
        for(auto it = m.begin();it != m.end();it++) {
            num += it->second[0];   
            num -= it->second[1];
            
            if(num > 2) {
                f = false;
                break;
            }
        }
        
        if(!f) {
            m[start][0]--;
            m[end][1]--;
            return false;
        }
        
        return true;
    }
};
/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

LeetCode : 2389. Longest Subsequence With Limited Sum

// binary search
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        vector<int> ans;
        
        sort(nums.begin(), nums.end());
        
        vector<int> pres = vector<int>(nums.size(), 0);
        pres[0] = nums[0];
        for(int i = 1;i < nums.size();i++) {
            pres[i] = pres[i - 1] + nums[i];
        }
        
        for(int i = 0;i < queries.size();i++) {
            int left = 0;
            int right = pres.size() - 1;
            int tmp = 0;
            while(left <= right) {
                int mid = (left + right) / 2;
                if(pres[mid] <= queries[i]) {
                    tmp = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            ans.push_back(tmp);
        }
        
        return ans;
    }
};

LeetCode : 2485. Find the Pivot Integer

class Solution {
public:
    int getSum(int left, int right) {
        return (left + right) * (right - left + 1) / 2;
    }
    int pivotInteger(int n) {
        int left = 1;
        int right = n;
        while(left <= right) {
            int mid = (left + right) / 2;
            int leftS = getSum(1, mid);
            int rightS = getSum(mid, n);
            
            if (leftS < rightS) {
                left = mid + 1;
            } else if(leftS > rightS) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
};