第K大的数

第K大的数
1.快排：每次返回的是标准的index，当index=k-1时就返回，不是就遍历一边
2.堆排序：对k个元素建立一个最小堆，然后遍历，比root大的就替换，这样部分排序
上面两个方法的复杂度都是nlogk

下一个排列

    void nextPermutation(vector<int>& nums) {
    //从后面数找到a[i-1] 小于 a[i]的i
    //从后面找大于a[i-1]的数a[j]
    //换一下a[i-1] 和 a[j]
    //然后反转 i到结尾
        int n=nums.size();
        if(n<=1) return;
        int i=n-1,j=n-1;
        while(i>0 && nums[i]<=nums[i-1]) i--;
        if(i==0){
            reverse(nums.begin(), nums.end());
            return;
        }
        while(j>0 && nums[j]<=nums[i-1]) j--;
    
        int tmp=nums[i-1];
        nums[i-1]=nums[j];
        nums[j]=tmp;
        //for(auto i:nums) cout<<i<<endl;
        reverse(nums.begin()+i,nums.end());
    }

缺失的第一个正数

    int firstMissingPositive(vector<int>& a) {
        int n=a.size();
        if(n==0) return 1;
        for(int i=0;i<n;++i){
            while(a[i]>0 && a[i]<(i+1) && a[a[i]-1]!=a[i]){  //注意这里的条件
                swap(a[a[i]-1], a[i]);
            }
        }
        for(int i=0;i<n;++i){
            if(a[i]!=(i+1)){
                return i+1;
            }
        }
        return n+1;
    }

第k个排列

 string getPermutation(int n, int k) {
        string num="123456789";
        int a[n]={1};
        string res;
        for(int i=1;i<n;++i){
            a[i]=a[i-1]*i;
        }
        k--;
        for(int i=n;i>=1;i--){
            int j = k / a[i-1];
            k = k % a[i-1];
            res.push_back(num[j]);  //string也用push_back，erase用法
            num.erase(j,1);
        }
        return res;
    }

数组中重复的元素

一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素
思路：从第一个节点开始，找到a[0]应该在的位置，一直循环，知道需要交换的两个数相等。和消失的第一个正数很像。

计算数组左侧(右侧)小于当前值的元素个数

思路：
从左往右遍历，将每次遍历过后的数放入另外一个数组temp中，使其保持有序。在计算右侧小于当前元素的个数，用二分查找的方式查找temp这个有序array，那么在数组左边的数即是小于当前元素的数，其位置index既为个数信息

var countSmaller = function(nums) {
    //temp升序
    var temp=[];
    var result=[];
    for(var i=nums.length-1;i>=0;i--)
    {
        //console.log(temp);
        var left=0;
        var right=temp.length;
        while(left<right)
        {
            var mid=left+parseInt((right-left)/2);
            if(temp[mid]>=nums[i])
                right=mid;
            else
                left=mid+1;
 
        }
        result[i]=left;
        temp.splice(left,0,nums[i]);
    }
    return result;
 
};