算法（五）

1、一堆螺丝和螺母用最短时间匹配。

//分类函数
//n和b为两个数组
//left为左索引，right为右索引
void Fix(int *n, int *b, int left, int right)
{
    if (left < right)
    {
        int tmp = n[left];
        int i = left, j = right;
        while (i < j)
        {
            while (i < j&&b[i] < tmp)
            {
                i++;
            }
            while (i < j&&b[j] > tmp)
            {
                j--;
            }
            if (i < j)
            {
                swap(b[i], b[j]);
            }
        }
        b[i] = tmp;
        swap(b[left], b[i]);
        cout << "n+b:" << endl; Print(n); Print(b); cout << endl;
        //一趟下来，i=j的tmp的位置。以tmp为界限，左右分别是小于和大于它的元素

        tmp = b[left + 1];
        i = left + 1, j = right;
        while (i < j)
        {
            while (i < j&&n[i] < tmp)
            {
                i++;
            }
            while (i < j&&n[j] > tmp)
            {
                j--;
            }
            if (i < j)
            {
                swap(n[i], n[j]);
            }
        }
        n[i] = tmp;
        swap(n[left + 1], n[i]);
        cout << "n+b:" << endl; Print(n); Print(b); cout << endl;

        Fix(n, b, left + 2, i);
        Fix(n, b, i + 1, right);
    }

}

时间复杂度：O(nlogn)

空间复杂度：O(1)

2、链表倒数第K个数

public int FindKthToTail(ListNode head, int k){

           ListNode pre =null, p=null;

           //两个指针均指向头结点

           p=head;

           pre = head;

           //记录k值

           int a = k;

           //记录节点的个数

           int count = 0;

           //p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，当p指针跑到最后时，pre指针所指向的节点               就是倒数第k个节点。

           while(p){

                    p = p.next;

                    count ++;

                    if(k < 1){

                             pre = pre.next;

                     }

                     k--;

           }

           if(count < a) return null;

           return pre.val;

}