分治方法 about basic-programming-knowledge HOT 2 CLOSED

第k小的数字
function minK(num, k) {
  k = k - 1;
  function partial(num, start, end) {
    let pivot = num[start];
    while (start < end) {
      while (start < end && num[end] > pivot) end--;
      if (start < end) {
        num[start] = num[end];
        start++;
      }
      while (start < end && num[start] < pivot) start++;
      if (start < end) {
        num[end] = num[start];
        end--;
      }
    }
    num[start] = pivot;

    return start;
  }

  function findK(start, end) {
    let mid = partial(num, start, end);
    if (mid === k) return num[mid];
    if (mid > k) return findK(start, mid - 1);
    if (mid < k) return findK(mid + 1, end);
  }

  return findK(0, num.length - 1);
}

let arr = [1, 234, 4, 23, 88, 34, 90, 45, 63, 2, 3, 4, 555, 6, 7, 8, 10, 9];
console.log(arr);
console.log(minK(arr, 18));
console.log(arr.sort((a, b) => a - b));

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (!lists || !lists.length) return null
    // 合并两排序链表
    function mergeTwo(a, b) {
        if (!a) return b;
        if (!b) return a;

        let head = new ListNode(0);
        let tail = head;

        while (a && b) {
            if (a.val < b.val) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = (a ? a : b);
        return head.next;
    }

    // 分治算法 两两合并
    function division(lists, l, r) {
        if (!lists) return null;
        if (l === r) return lists[l]
        let all = [];
        while(l < r) {
            all.push(mergeTwo(lists[l++], lists[r--]));
        }
        if (l === r) all.push(lists[l])

        return division(all, 0, all.length - 1)
    }

    return division(lists, 0, lists.length - 1)
};