leetcode 870. 優勢洗牌（田忌賽馬問題）

分析

主要是是一個貪心問題，先對A進行排序，每次在A中尋找大于B[i]的最小值，若沒有，則傳回A中的最小值。

multiset的作用

維持一個有可重複的有序的set, 友善查找和動态删除，且删除之後仍然是有序的。

方法1

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
        multiset<int> ans_A;
        if(A.size()==0) return res;
        //将A放到一個multiset中
        for(int i=0;i<A.size();i++) ans_A.insert(A[i]);
        for(int i=0;i<B.size();i++){
            bool flag = false;      
            //周遊ans_A
            for(auto it = ans_A.begin();it!=ans_A.end();it++){
                if(*it>B[i]){
                    res.push_back(*it);
                    ans_A.erase(it);
                    flag = true;
                    break;
                }
            }  
            if(!flag){
                res.push_back(*ans_A.begin()); 
                ans_A.erase(ans_A.begin());
            }
        }
        return res;
    }
};
           

方法2：

上面的方法是逾時的，考慮使用标記數組的方式。雖然是多過了幾個用例仍是逾時。

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
        if(A.size()==0) return res;
        //對A進行排序
        sort(A.begin(), A.end());
        vector<int> f(A.size(), 0);
        int index = 0;//表示已經使用的A的較小值的索引結尾
        for(int i=0;i<B.size();i++){
            bool flag = false;      
            //周遊ans_A
            for(int j=0;j<A.size();j++){//j也可以從index開始
                if(A[j]>B[i] && !f[j]){
                    res.push_back(A[j]);
                    flag = true;
                    f[j] = 1;
                    break;
                }
            }  
            if(!flag){
                while(f[index]) index++;
                f[index] = 1;
                res.push_back(A[index++]); 
            }
        }
        return res;
    }
};
           

方法3：

不使用multiset, 使用vector+ 二分查找+erase删除元素。為什麼不使用multiset+二分查找，主要是因為multiset不支援順序疊代器通路，是以在使用二分查找之後，不好進行删除元素。

class Solution {
public:
    int binary_search(vector<int>& arr, int target){
        int l = 0;
        int r = arr.size();
        while(l<r){
            int mid = l + (r-l)/2;
            int mid_value = arr[mid];
            if(mid_value<=target){//找第一個比target大的
                l = mid+1;
            }else r = mid;
        }
        return l;
    }
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
        if(A.size()==0) return res;
        sort(A.begin(), A.end());
        for(int i=0;i<B.size();i++){
            int l = binary_search(A, B[i]);
            if(l==A.size()){//沒有找到
                res.push_back(*A.begin()); 
                A.erase(A.begin());
            }
            if(l<A.size()){
                res.push_back(A[l]);
                A.erase(A.begin()+l);
            }
        }
        return res;
    }
};