TopK问题

Sort 得2分

let findKthLargest = function(nums, k) {
nums.sort((a, b) => b - a).slice(0, k);
return nums[k-1]
}

时间复杂度:O(nlogn)

空间复杂度:O(logn)

sort方法在数组长度小于10的时候，在V8 7.0以下版本使用的是快速排序，在7.0+以上舍弃快速排序因为其不稳定，时间复杂度退化为O(n ^ 2)

冒泡排序得5分

let findKthLargest = function (nums, k) {
  // 进行k轮冒泡
  bubbleSort(nums, k);
  return nums[nums.length - k];
};
let bubbleSort = function (arr, k) {
  for (let i = 0; i < k; i++) {
    // 提前退出循环的标识
    let flag = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        flag = true;
        // 发生数据交换
      }
    }
    // 没有数据交换
    if (!flag) break;
  }
};
var items = [1, 9, 2, 8, 3, 7, 4, 6, 5];
console.log(findKthLargest(items, 4));

时间复杂度:O(nk)，最好O(n)

空间复杂度:O(1)

快速排序得5分

let quickSort = (arr) => {
  quick(arr, 0, arr.length - 1);
  return arr;
};
let quick = (arr, left, right) => {
  let index;
  if (left < right) {
    // 划分数组
    index = partition(arr, left, right);
    // 对index左边的继续进行快速排序
    if (left < index - 1) {
      quick(arr, left, index - 1);
    }
    if (index < right) {
      quick(arr, index, right);
    }
  }
};
// 一次快排
let partition = (arr, left, right) => {
  // 中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
    i = left,
    j = right;
  // 开始调整
  while (i <= j) {
    // 左指针右移
    while (arr[i] < datum) {
      i++;
    }
    // 右指针左移
    while (arr[j] > datum) {
      j--;
    }
    // 交换
    if (i <= j) {
      swap(arr, i, j);
      i += 1;
      j -= 1;
    }
  }
  return i;
};

let swap = (arr, i, j) => {
  [arr[i], arr[j]] = [arr[j], arr[i]];
};
var items = [1, 9, 2, 8, 3, 7, 4, 6, 5];
console.log(quickSort(items)[items.length - k]);

时间复杂度:O(nlogn)

空间复杂度:O(logn)

堆排序得8分

不懂堆排序的先去这里看清楚原理

直接上代码

// 只用稍微修改一下堆排序的代码即可
- function heapSort(items) {
+ function heapSort(items, k) {
  let heapSize = items.length;
  // 构建好了一个大顶堆
  buildHeap(items, heapSize);
	// 进行下沉 大顶堆是最大元素下沉到末尾
- for (let i = items.length - 1; i >= 0; i--) {
+ for (let i = items.length - 1; i >= items.length - k + 1; i--) {  
    swap(items, 0, i);
    // 下沉后的元素不参与到大顶堆的调整
    --heapSize;
    // 重新调整大顶堆
    maxHeapify(items, 0, heapSize);
  }
- return items;
+ return items[0];
}
// 自下而上构建一颗大顶堆
function buildHeap(items, heapSize) {
  for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
    maxHeapify(items, i, heapSize);
  }
}
// 从左向右，自上而下的调整节点
function maxHeapify(items, i, heapSize) {
  let l = 2 * i + 1;
  let r = 2 * i + 2;
  let large = i;
  if (l < heapSize && items[l] > items[large]) {
    large = l;
  }
  if (r < heapSize && items[r] > items[large]) {
    large = r;
  }
  if (large !== i) {
    swap(items, large, i);
    // 继续调整下面的非叶子节点
    maxHeapify(items, large, heapSize);
  }
}
function swap(items, i, j) {
  [items[i], items[j]] = [items[j], items[i]];
}

var items = [1, 9, 2, 8, 3, 7, 4, 6, 5];
console.log(heapSort(items, 4));

时间复杂度:遍历数据需要O(n),一次堆化需要O(logk),所以为O(nlogk)

空间复杂度:O(k)

快速选择排序得9分

对快速排序进行优化

我们只用找到第k个最大值，没必要排序整个数组

• 如果小于n - k,则第k个最大值在index右边，只需要递归遍历右边的就行了
• 繁殖如果大于n - k，那就递归遍历左边
• 如果等于n - k，那第k个最大值就在index处

let quickSort = (arr, k) => {
  return quick(arr, 0, arr.length - 1, arr.length - k);
};
let quick = (arr, left, right, k) => {
  let index;
  if (left < right) {
    // 划分数组
    index = partition(arr, left, right);
    if (k === index) return arr[index];
    else if (k < index) return quick(arr, left, index - 1, k);
    else return quick(arr, index + 1, right, k);

    //  if (left < index - 1) {
    //     quick(arr, left, index - 1);
    //   }
    //   if (index < right) {
    //     quick(arr, index, right);
    //   }
  }
  return arr[left];
};
// 一次快排
let partition = (arr, left, right) => {
  // 中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
    i = left,
    j = right;
  // 开始调整
  while (i < j) {
    // 左指针右移
    while (arr[i] < datum) {
      i++;
    }
    // 右指针左移
    while (arr[j] > datum) {
      j--;
    }
    // 交换
    if (i < j) swap(arr, i, j);
    // 当数组存在重复数据且都为datum，但是位置不同时，继续递增i，防止死循环
    if (arr[i] === arr[j] && i !== j) i++;
  }
  return i;
};

let swap = (arr, i, j) => {
  [arr[i], arr[j]] = [arr[j], arr[i]];
};
var items = [1, 9, 2, 8, 3, 7, 4, 6, 5];
console.log(quickSort(items, 4));

时间复杂度:平均O(n)，最坏O(n^2)

空间复杂度:O(1)