2025.02.17~2025.02.21

/**
 * 找到数组中第k大的元素
 * 分析：
 *  1. 可以直接对数组进行排序，然后取出第k大的元素。
 *  2. 题目中提到找到第k大的元素吗，那么可以使用最小堆来维护k个最大的元素，堆顶元素就是第k大的元素。
 *  3. 进一步优化，可以使用快速排序的思想，使用pivot先进行分区，然后确定n-k个元素在pivot的哪边，只需要对那一边进行递归即可。递归的终止条件是k === n - k。
 */
/**
 * 第一种解法，采用冒泡排序进行排序然后取第k大的元素
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 */
// function findKthLargest(nums: number[], k: number) {
//   for (let i = 0; i < nums.length; i++) {
//     for (let j = i + 1; j < nums.length; j++) {
//       // 将 i 挨个与 j 对比，i 大则交换他们的位置，直到尾部
//       if (nums[i] > nums[j]) {
//         [nums[i], nums[j]] = [nums[j], nums[i]];
//       }
//     }
//   }
//   return nums[nums.length - k];
// }

/**
 * 第一种解法再优化，冒泡排序的时间复杂度过高，使用快速排序代替
 */
// function partition(nums: number[], left: number, right: number) {
//   const pivot = nums[left];
//   let i = left;
//   let j = right + 1;

//   while (i < j) {
//     do {
//       i++;
//     } while (nums[i] < pivot);

//     do {
//       j--;
//     } while (nums[j] > pivot);

//     if (i < j) {
//       [nums[i], nums[j]] = [nums[j], nums[i]];
//     }
//   }

//   [nums[left], nums[j]] = [nums[j], nums[left]];
//   return j;
// }

// function quickSort(nums: number[], left: number, right: number) {
//   if (left >= right) return;
//   // 找到基准值下标
//   const pivot = partition(nums, left, right);
//   quickSort(nums, left, pivot - 1);
//   quickSort(nums, pivot + 1, right);
// }

/**
 * 时间复杂度：O(nlogn)，为什么？logn 是因为每次都是对一半的元素进行递归，n 是因为每次都需要遍历所有元素
 * 空间复杂度：O(logn)，递归调用栈的深度
 */
// export function findKthLargest(nums: number[], k: number) {
//   quickSort(nums, 0, nums.length - 1);
//   return nums[nums.length - k];
// }

/**
 * 第二种解法，最小堆，维护k大小的最小堆
 * 时间复杂度：O(nlogk)，为什么？n 是遍历所有元素，logk 是因为每次都需要维护一个大小为 k 的最小堆
 * 空间复杂度：O(k)，最小堆的大小
 */
// class MinHeap {
//   private heap: number[];

//   constructor() {
//     this.heap = [];
//   }

//   left(index: number) {
//     return this.heap[2 * index + 1];
//   }

//   right(index: number) {
//     return this.heap[2 * index + 2];
//   }

//   parent(index: number) {
//     return this.heap[Math.floor((index - 1) / 2)];
//   }

//   peek() {
//     return this.heap[0];
//   }

//   insert(val: number) {
//     this.heap.push(val);
//     this.heapifyUp();
//   }

//   extractMin(n: number) {
//     this.heap[0] = n;
//     this.heapifyDown();
//   }

//   size() {
//     return this.heap.length;
//   }

//   /**
//    * 步骤是什么？
//    *  1. 找到最后一个非叶子节点
//    *  2. 从最后一个非叶子节点开始，向上比较子节点和父节点的大小，如果子节点大于父节点，则交换子节点和父节点的值
//    *  3. 重复步骤2，直到根节点
//    *  4. 重复步骤1和步骤2，直到堆有序
//    */
//   private heapifyUp() {
//     let index = this.heap.length - 1;
//     while (index > 0) {
//       const parentIndex = Math.floor((index - 1) / 2);
//       if (this.heap[index] < this.heap[parentIndex]) {
//         [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
//         index = parentIndex;
//       } else {
//         break;
//       }
//     }
//   }

//   /**
//    * 步骤是什么？
//    *  1. 从根节点开始，比较当前节点和左右子节点的值
//    *  2. 如果当前节点比左右子节点都大，则交换当前节点和左右子节点中的最小值
//    *  3. 重复步骤1和2，直到堆的每个节点都满足堆的性质
//    *  4. 最终得到一个有序的堆
//    *
//    */
//   heapifyDown() {
//     let index = 0;
//     while (index < this.heap.length) {
//       const leftIndex = 2 * index + 1;
//       const rightIndex = 2 * index + 2;
//       let smallest = index;
//       if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[smallest]) {
//         smallest = leftIndex;
//       }
//       if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[smallest]) {
//         smallest = rightIndex;
//       }
//       if (smallest !== index) {
//         [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
//         index = smallest;
//       } else {
//         break;
//       }
//     }
//   }
// }

// function findKthLargest(nums: number[], k: number) {
//   const heap = new MinHeap();
//   for (let i = 0; i < nums.length; i++) {
//     if (heap.size() < k) {
//       heap.insert(nums[i]);
//     } else if (nums[i] > heap.peek()) {
//       heap.extractMin(nums[i]);
//     }
//   }
//   return heap.peek();
// }

/**
 * 第三种解法，快速选择算法
 * 时间复杂度：平均 O(n)，最坏 O(n^2)。
 *  - 平均 O(n) 是因为每次都是对一半的元素进行递归。
 *  - 最坏 O(n^2) 是因为可能会遇到最坏情况，每次都是对 n-1 个元素进行递归。
 * 空间复杂度：O(1)。
 */
function findKthLargest(nums: number[], k: number) {
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(nums: number[], left: number, right: number, k: number) {
  // 递归函数的终止条件
  if (left === right) return nums[left];

  // 分区操作，找到基准值下标
  const pivot = nums[left];
  let pivotIndex = left;
  let i = left;
  let j = right + 1;

  while (i < j) {
    do {
      i++;
    } while (nums[i] < pivot);

    do {
      j--;
    } while (nums[j] > pivot);
    if (i < j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  [nums[left], nums[j]] = [nums[j], nums[left]];
  pivotIndex = j;
  if (k === pivotIndex) {
    return nums[k];
  } else if (k < pivotIndex) {
    // 如果 k 小于 pivotIndex，则说明第 k 大的元素在 pivotIndex 的左边
    return quickSelect(nums, left, pivotIndex - 1, k);
  } else {
    // 如果 k 大于 pivotIndex，则说明第 k 大的元素在 pivotIndex 的右边
    return quickSelect(nums, pivotIndex + 1, right, k);
  }
}