HackerRank‐Sorting - a920604a/leetcode GitHub Wiki

void countSwaps(vector<int> a) {
    int count = 0;
    int n = a.size();
    for(int i=0;i<n-1;++i){
        for(int j=i;j<n;++j){
            if(a[j]< a[i]){
                swap(a[j], a[i]);
                count++;
            }
        }
    }
    cout<<"Array is sorted in "<< count<< " swaps."<<endl;
    cout<<"First Element: "<<a[0]<<endl;
    cout<<"Last Element: "<<a.back()<<endl;
}

int maximumToys(vector<int> prices, int k) {
    sort(prices.begin(), prices.end());
    int n = prices.size();
    //  1   2   3   4   , 7
    int count= 0;
    for(int i=0;i<n;++i){
        if(k>= prices[i]){
            k-=prices[i];    
        }
        else{
            count = i;
            break;
        }
    }
    return count;
}

class Checker{
public:
  	// complete this method
    static int comparator(Player a, Player b)  {
        if(a.score == b.score) return a.name < b.name?1:-1;
        return a.score > b.score ? 1:-1;
    }
};

double median(vector<int> &window, int size){
    if(size%2==0){
        int l=0, r=0;
        int cur = size/2;
        for(int i=0;i<201 ; ++i){
            if(cur - window[i]==0){
                l = i;
                i++;
                while(i<201 && window[i]==0) i++;
                return (double)(l+i)/2.0;
                
            }
            else if(cur - window[i] > 0) cur-=window[i];
            else if(cur - window[i] < 0) return i;
        }
    }
    else{
        int a = size/2;
        for(int i=0;i<201 ;++i){
            if(a-window[i]<0) return i;
            else a-=window[i];
        }
    }
    return -1;
}
int activityNotifications(vector<int> expenditure, int d) {
    vector<int> windows(201, 0);
    int count =0;
    for(int i=0;i<d;++i) windows[expenditure[i]]++;
    for(int i=d;i<expenditure.size() ; ++i){
        double med = median(windows, d);
        if(expenditure[i] >= 2*med) count++;
        // update windows
        windows[expenditure[i]]++;
        windows[expenditure[i-d]]--;
    }
    return count;
}

void Merge(vector<int> & nums, int l, int mid, int r, long & count){
    if(l>=r) return;
    int i=l, j =mid+1;
    vector<int> ret;
    while(i<=mid && j<=r ){
        if (nums[i] <= nums[j]){
            ret.push_back(nums[i++]);
        }
        else{
            count+=(mid-i+1);
            ret.push_back(nums[j++]);
        }
    }
    while(i<=mid) ret.push_back(nums[i++]);
    while(j<=r) ret.push_back(nums[j++]);
    for(int i=l;i<=r;++i) nums[i] = ret[i-l];
    
}
void MergeSort(vector<int> & nums,int l,int r ,long & count){
    if(l>=r) return;
    int mid = l + (r-l)/2;
    MergeSort(nums, l, mid, count);
    MergeSort(nums, mid+1, r, count);
    Merge(nums, l, mid, r, count);
    
}