Leetcode - 数组

class Solution {
public:
    /**
    实际上只需要关注相等的数
    */
    int numIdenticalPairs(vector<int>& nums) {
        sort(nums.begin(), nums.end())   ;
        int sum=0;
        int i=0, j=0;
        while(i < nums.size()){
            int cnt=0;
            while(j < nums.size() && nums[j] == nums[i]){
                cnt++;
                j++;
            }
            i = j;
            sum += cnt * (cnt-1) / 2;
        }
        return sum;
    }
};

class Solution {
public:
    /**
    根据题目限定，可以不排序
    */
    int count[101];
    int numIdenticalPairs(vector<int>& nums) {
        int sum=0;
        for(int i=0; i<nums.size(); i++)
            sum += (count[nums[i]]++);
        return sum;
    }
};

class Solution {
public:
    int cnt[101];
    int dp[101];
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            cnt[nums[i]]++;
        }
        for(int i=1; i<101; i++){
            dp[i] = dp[i-1] + cnt[i-1];
        }
        for(int i=0; i<nums.size(); i++){
            nums[i] = dp[nums[i]];
        }
        return nums;
    }
};

class Solution {
public:
    /**
    对于发生递减的两个数，需要删除的数可能是其中之一
    比如  3 (4 3) 5 6 需要去掉前一个4
    比如  3 (5 4) 5 6 需要去掉后一个4
    */
    bool checkPossibility(vector<int>& nums) {
        bool flag = false;
        for(int i=0; i<nums.size()-1; i++){
            if(nums[i] > nums[i+1]){
                if(flag) return false;
                bool pre = true, tail = true;
                if(i > 0 && nums[i-1] > nums[i+1])
                    pre = false;
                
                if(i+1 < nums.size()-1 && nums[i] > nums[i+2])
                    tail = false;
                
                if(pre || tail) flag = true;
                else return false;
            }
        }
        return true;
    }
};

class Solution {
public:

    void duplicateZeros(vector<int>& arr) {
        /*统计出现的零的个数*/
        int zeros = 0;
        for(int i=0; i<arr.size(); i++){
            if(arr[i] == 0) zeros++;
        }
        /*i指向原本数组，j指向新的数组，i指向0，j能写的话就写两遍*/
        for(int i=arr.size()-1, j = i+zeros; i>-1; i--, j--){
            if(arr[i] == 0) {
                if(j<arr.size()) arr[j] = arr[i];
                j--;
                if(j<arr.size()) arr[j] = arr[i];
            }else{
                if(j<arr.size()) arr[j] = arr[i];
            }
        }
    }
};

class Solution {
public:
    /**
    一个数组，假设下标从1开始，第i个数如果是x(x>i)，说明之前少了x-i个数。比如
    1 2 4
    第3个数是4，说明之前少了4-3=1个数
    
    只要找到最大的i使得第i个数之前缺失了j个数满足j<k，i+k就是第k个缺失的数 迷惑，为啥
    
    
    */
    int findKthPositive(vector<int>& arr, int k) {
        int l=0, r=arr.size();
        while(l<r){
            int mid = (l+r) >> 1;
            if(arr[mid]-mid-1 < k)
                l=mid+1;
            else
                r=mid;
        }
        return l+k;
    }
};