排序

56-合并区间
57-插入区间

字典序排数

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        int cur = 1;
        for (int i = 0; i < n; ++i) {
            res[i] = cur;
            if (cur * 10 <= n) {
                cur *= 10;
            } else {
                if (cur >= n) cur /= 10;
                cur += 1;
                while (cur % 10 == 0) cur /= 10;
            }
        }
        return res;
    }
//dfs
vector<int> lexicalOrder(int n) {
        vector<int> res;
        for(int i=1;i<=9;i++)
            dfs(i,n);
        return res;
    }
    void dfs(int i,int n){
        if(i>n) return;
        res.push_back(i);
        
        for(int j=0;j<=9;j++)
            dfs(i*10+j,n);
    }

字典序的第K小数字

输入:
n: 13 k: 2
输出:
10
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10

思路分析：请先翻阅 LeetCode 字典序排数
上一道题是要给出排序的数列，所以需要遍历每一个数字。而此次只是寻找，并不要访问每一个，
因此不能采用上一道题的暴力递归。其实这个字典数是“十叉树”，就是每个节点可以有十个孩子。
但是由于n大小的限制，构成的并不是一个满十叉树。比如示例中1只有[10,11,12,13]四个孩子。
那么这就是先序遍历十叉树的问题，难点就变成了如何计算出每个节点的子节点的个数，
我们不停的用k减去子节点的个数，当k减到0的时候，当前位置的数字即为所求。
 int findKthNumber(int n, int k) {
        int cur = 1;
        --k;//初始化为cur = 1，k需要自减1
        while (k > 0) {
            long long step = 0, first = cur, last = cur + 1;
            //统计这棵子树下所有节点数（step）
            while (first <= n) {
                step += min((long long)n + 1, last) - first;//不能超过n的值，并不是所有节点都有十个子节点
                first *= 10;
                last *= 10;
            }
            if (step <= k) {//不在子树中
                ++cur;
                k -= step;
            } 
            else {//在子树中，进入子树
                cur *= 10;
                --k; 
            }
        }
        return cur;
    }

快排

void quick_sort(int *a, int left, int right){
    if(left < right){
        int i=left,j=right,num=a[left];
        while(i<j){
            while(i<j && a[j]>=num) j--;
            if(i<j) a[i++]=a[j];
            while(i<j && a[i]<num) i++;
            if(i<j) a[j--]=a[i];
        }
        a[i]=num;
        quick_sort(a,left,i-1);
        quick_sort(a,i+1,right);
    }
}

链表的快排

    ListNode* sortList(ListNode* head) {    
        quicksort(head,NULL);
        return head;
    }
    void quicksort(ListNode* head, ListNode* end){
        if(head != end){
            ListNode* mid = partitions(head);
            quicksort(head, mid);
            quicksort(mid->next, end);
        }
    }    
    ListNode* partitions(ListNode* head){
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast != NULL){
            if(fast->val < head->val){
                slow = slow->next;
                swap(slow->val, fast->val);
            }
            fast=fast->next;
        }
        swap(slow->val, head->val);
        return slow;
    }

堆排序

//6,1,3,2,7,4,5
//count=7
void heapSort(int *num, int n) {
    for(int i=n/2-1;i>=0;i--){
        max_heap(num,i,n);
    }
    for(int i=n-1;i>0;i--){
        swap(num[i],num[0]);
        max_heap(num,0,i);
    }
}
void max_heap(int *a,int i, int n){
    int tmp=a[i];
    for(int k=i*2+1;k<n;k=k*2+1){
       if(k+1<n && a[k]<a[k+1]) k++;
       if(a[k]>tmp){
           a[i]=a[k];
           i=k;
       }else{
           break;
       }
   }
   a[i]=tmp;
}

归并排序

void Merge(int *A,int *L,int leftCount,int *R,int rightCount) {
    int i,j,k;
    i = 0; j = 0; k =0;
 
    while(i<leftCount && j< rightCount) {
        if(L[i]  < R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }
    while(i < leftCount) A[k++] = L[i++];
    while(j < rightCount) A[k++] = R[j++];
}
 
void MergeSort(int *A,int n) {
    int mid,i, *L, *R;
    if(n < 2) return; 
 
    mid = n/2; 
    L = new int[mid];
    R = new int [n - mid];
 
    for(i = 0;i<mid;i++) L[i] = A[i]; 
    for(i = mid;i<n;i++) R[i-mid] = A[i]; 
 
    MergeSort(L,mid);  
    MergeSort(R,n-mid);  
    Merge(A,L,mid,R,n-mid);  
    delete [] R;
    delete [] L;
}