排序算法笔记

  • 开发
  • 36

排序算法

常用排序算法

快速排序（Quicksort）

快速排序是一种非常高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer）。在待排序的数组中选择一个元素作为基准（pivot），然后将数组分为两部分：一部分包含小于基准的元素，另一部分包含大于基准的元素。这个过程称为分区（partition）。接下来，递归地对这两部分继续进行快速排序，直到整个序列有序。

快速排序的关键步骤是分区操作，其算法过程大致如下：

  1. 选择基准值：从数组中选择一个元素作为基准值，不同的选择方法可能会影响算法的性能。常见的基准选择方法有：选择第一个元素、选择最后一个元素、随机选择一个元素、选择中位数等。
  2. 分区操作：重新排列数组，使得所有小于基准值的元素都移动到基准值的左边，所有大于基准值的元素都移动到基准值的右边。分区结束后，基准值处于其最终位置。
  3. 递归排序：递归地将小于基准值的部分和大于基准值的部分分别进行快速排序。

快速排序的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)，当输入数组已经是正序或逆序时会出现最坏情况。通过一些策略，如随机化基准，可以大幅度降低这种最坏情况出现的概率。

下面是一个简单的快速排序C++实现的示例：

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于pivot
        if (arr[j] <= pivot) {
            i++; // 增加小于pivot的元素的索引
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

在这个实现中，partition函数负责执行分区操作，quickSort函数通过递归调用自身来对分区后的子数组进行排序。最终，整个数组就被排序。这个示例中选择了数组的最后一个元素作为基准值。

这段代码实现了快速排序算法，包括两个主要的函数：quickSort和partition。让我们逐步分析这两个函数的工作原理。

quickSort 函数

quickSort是快速排序算法的主体函数，负责递归地对数组的子段进行排序。

  • 参数：它接受三个参数：一个整数数组arr的引用，以及两个整数low和high，分别表示当前需要排序子数组的最低索引和最高索引。
  • 递归的基准条件：如果low < high，表示当前子数组至少有两个元素，需要进行排序。如果low大于等于high，递归就会停止，因为这意味着子数组不需要排序（已经是有序的或者为空）。
  • 分区操作：通过调用partition函数，以high作为基准（pivot），将数组分为两部分。partition函数返回基准元素的最终位置pivot，这个位置是基准元素排序后应处于的正确位置。
  • 递归排序：分别对基准元素左侧和右侧的子数组递归地进行快速排序。quickSort(arr, low, pivot - 1)对基准元素左边的子数组进行排序，而quickSort(arr, pivot + 1, high)对右边的子数组进行排序。
partition 函数

partition函数是快速排序算法的核心，负责对数组进行分区，即重新排列数组元素，使得左边的元素都不大于基准值，右边的元素都大于基准值。

  • 参数：与quickSort相同，接受数组的引用及子数组的最低和最高索引low和high。
  • 基准选择：选择arr[high]作为基准值pivot。这是一种常见的选择方法，但并不是唯一的方法。
  • 索引i的初始化：i被初始化为low - 1，表示当前找到的最右侧的不大于基准值的元素的索引。
  • 遍历和交换：通过一个循环遍历low到high - 1之间的每个元素，与基准值比较。如果当前元素arr[j]不大于基准值，则i增加，并将arr[i]和arr[j]交换位置，这样可以确保i左边的所有元素都不大于基准值。
  • 基准值归位：循环结束后，将基准值交换到其最终位置i + 1，此时，arr[i + 1]左边的所有元素都不大于基准值，右边的所有元素都大于基准值。
  • 返回值：函数返回基准值的最终位置i + 1，供quickSort函数进行下一步的递归排序。

这种分区逻辑是快速排序算法高效性的关键所在，它使得每一次partition调用都能确保至少有一个元素（即基准元素）被放置在其最终位置，同时对数组进行部分排序，从而减少后续需要排序的元素数量。通过递归地应用这一过程，最终能够达到整个数组的排序。

归并排序（Merge Sort）

归并排序是一种分治算法，其核心思想是将一个大数组分成两个小数组去解决。归并排序先递归地将数组分成两半进行排序，然后将两个有序的子数组合并成一个完整的有序数组。这种方法非常适用于大数据集，因为它的最坏时间复杂度和平均时间复杂度都是O(n log n)，并且它是稳定的排序方法。

归并排序的主要步骤分为两部分：分解和合并。

  1. 分解：将当前序列分成两个长度大致相等的子序列。
  2. 递归排序：递归地对这两个子序列进行归并排序。
  3. 合并：将两个有序的子序列合并成一个完整的有序序列。

归并操作（Merge）是归并排序的核心步骤，它将两个有序的数组合并成一个大的有序数组。这个过程通常需要额外的空间来存储合并后的数组。

下面是归并排序算法的C++实现：

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序子数组的函数
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    // 合并两个有序数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 复制剩余的元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将合并后的数组复制回原数组
    for (i = left, k = 0; i <= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

// 归并排序函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    int arrSize = arr.size();

    cout << "Given array is \n";
    for(int i = 0; i < arrSize; i++)
        cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, arrSize - 1);

    cout << "Sorted array is \n";
    for(int i = 0; i < arrSize; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

在这个实现中，mergeSort函数是归并排序的递归函数，它接受一个数组和两个指示子数组范围的索引left和right。当这个子数组长度大于1时，函数会找到中点mid，递归地对左右两个子数组分别进行排序，最后调用merge函数将它们合并成一个有序数组。merge函数负责合并两个已排序的子数组。

这段代码实现了归并排序算法，包含两个主要函数：mergeSort和merge。让我们详细分析这两个函数的工作原理和归并排序的过程。

mergeSort 函数

这是归并排序的递归函数，用于对数组arr的指定区间[left, right]进行排序。

  • 参数：

    • arr：引用传递，表示待排序的数组。
    • left和right：表示当前排序区间的起始和结束索引。

  • 递归的基本逻辑：

    • 如果left < right，意味着区间内至少有两个元素，可以继续分解。
    • 计算中间索引mid = left + (right - left) / 2，这样做是为了防止(left + right)直接相加可能导致的整数溢出。
    • 对左半部分[left, mid]递归调用mergeSort。
    • 对右半部分[mid + 1, right]递归调用mergeSort。
    • 使用merge函数合并两个有序的子数组。
merge 函数

这个函数的目的是合并两个已经排序的连续子数组[left, mid]和[mid + 1, right]，以使得[left, right]区间内的元素有序。

  • 参数：

    • arr：待排序的数组，通过引用传递。
    • left、mid、right：分别表示要合并的两个子数组的起始、中间和结束索引。

  • 过程：

    • 创建一个临时数组temp，用于存放合并后的有序元素，大小为right - left + 1。
    • 使用两个指针i和j分别遍历两个子数组。i从left开始，用于遍历第一个子数组；j从mid + 1开始，用于遍历第二个子数组。k是temp数组的索引。
    • 在两个子数组都未遍历完的情况下，比较arr[i]和arr[j]的值，将较小的元素先复制到temp数组中，并移动相应的指针（i或j）和k。
    • 如果某一个子数组先遍历完，就将另一个子数组的剩余元素直接复制到temp数组中。
    • 最后，将temp数组中的元素复制回原数组arr的[left, right]区间，完成合并操作。

归并排序的特点

  • 分治策略：归并排序是典型的分治策略应用，通过递归地将问题分解为更小的问题解决，然后将这些小问题的解合并为原问题的解。
  • 稳定性：归并排序是一种稳定的排序算法，即相等的元素在排序后保持其原始顺序。
  • 空间复杂度：归并排序需要O(n)的额外空间，主要用于在合并过程中存储临时数组。

归并排序因其稳定的时间复杂度和出色的大数据集处理能力而广泛应用，在很多语言的排序库中都有其影子。

插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法，它的工作方式类似于我们排序手中的扑克牌。插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因其简单易懂和适用于小数据量排序，这使得它在这些场景中非常有效。

  • 插入排序的步骤：
  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。

  • 插入排序的特点：

  • 时间复杂度：最好情况O(n)，平均情况和最坏情况O(n^2)，其中n是数组的长度。

  • 空间复杂度：O(1)，因为只需要一个额外的空间进行交换。

  • 稳定性：插入排序是稳定的排序方法。

  • 适用场景：适合数据量小，或大部分元素已经排序的情况。

下面是插入排序的C++实现：

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将arr[i]插入到arr[0]...arr[i-1]中正确的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);

    cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

在这个实现中，insertionSort函数通过遍历数组中的每个元素（从第二个元素开始），并将它插入到它前面的已排序部分的正确位置来对数组进行排序。这通过在已排序的数组部分中向后移动元素来为新元素提供空间实现。

这段代码实现了插入排序算法，通过在C++中定义insertionSort函数来对一个整数类型的vector进行排序。下面是对这个过程的详细分析：

insertionSort(vector<int>& arr)函数
  • 参数：arr，一个整数vector的引用，代表待排序的数组。
  • 过程：
    • 循环遍历数组：从索引1开始，因为单个元素（即第一个元素）默认已经排序。i是当前要插入到已排序部分的元素的索引。
    • key存储当前元素：key = arr[i]，即当前需要被插入到已排序部分的元素。
    • 内部循环寻找key的正确位置：
      • 使用索引j从i-1开始向后遍历已排序的部分。
      • 向后移动元素：如果arr[j]大于key，则arr[j]向后移动一个位置到arr[j + 1]。
      • 插入key：当arr[j]不再大于key或j减小到0以下时，循环结束。此时，j+1就是key的正确位置，将key赋值给arr[j + 1]。

插入排序的特性和性能

  • 时间复杂度：在最坏的情况下（输入数组逆序），每次插入操作都要比较并移动所有之前的元素，因此时间复杂度为O(n^2)。在最好的情况下（输入数组已经是排序的），每次插入不需要移动之前的元素，时间复杂度为O(n)。
  • 空间复杂度：O(1)，因为排序是就地进行的，只需要有限的额外空间。
  • 稳定性：插入排序是稳定的，因为它不会改变相等元素的相对顺序。
  • 适用性：对于小规模数据或几乎已经排序的数据，插入排序是非常有效的。

通过这个简单但有效的方法，插入排序算法能够确保数组的每一步都是有序的，直至整个数组排序完成。

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较每对相邻元素，并在顺序错误的情况下交换它们。这个过程重复进行，直到没有需要交换的元素为止，这时列表就完全排序了。由于这个算法在最坏的情况下需要对列表进行多次完整的遍历，因此它不适合于数据量较大的排序应用。

  • 冒泡排序的基本步骤：
  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  • 冒泡排序的特点：

  • 时间复杂度：平均和最坏情况下都是O(n^2)，其中n是数组的长度。

  • 空间复杂度：O(1)，因为排序是就地进行的。

  • 稳定性：冒泡排序是稳定的排序方法。

  • 适用性：适合小数据量的排序，或者数据几乎已经是排好序的情况。

下面是冒泡排序的C++实现：

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换arr[j]和arr[j+1]
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // 如果这一轮没有发生交换，说明数组已经有序，可以提前退出
        if (!swapped)
            break;
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    cout << "Sorted array: \n";
    for(int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

这段代码通过定义bubbleSort函数实现了冒泡排序算法。算法的核心在于两层嵌套循环：外层循环每次迭代使未排序的最大元素"冒泡"到其在数组中的最终位置；内层循环进行相邻元素的比较和必要的交换。此外，引入了swapped标志位优化算法，如果在某次遍历中没有发生任何交换，则说明数组已经排序完成，可以提前结束循环，这样可以在最好的情况下达到O(n)的时间复杂度。

这段代码实现了冒泡排序算法，通过在C++中定义bubbleSort函数来对一个整数类型的vector进行排序。以下是对这个函数及其工作原理的详细分析：

bubbleSort 函数

  • 参数：arr，一个整数vector的引用，代表待排序的数组。

  • 过程：

    • 初始化变量n为数组的长度。
    • 使用一个bool类型的变量swapped来标记在内部循环中是否发生了交换操作。这是一个优化，旨在减少不必要的遍历，如果某一次遍历整个数组后没有发生任何交换，说明数组已经排序完成。
    • 外层循环（i从0到n-2）：控制排序的总轮数。每完成一轮，数组末尾的元素就是当前未排序部分的最大值。
    • 内层循环（j从0到n-i-2）：遍历未排序的数组部分，相邻元素进行比较，并在顺序错误时进行交换。
      • 如果arr[j] > arr[j+1]，则交换这两个元素的位置，并设置swapped = true。
    • 如果一次遍历完成后swapped仍为false，则提前退出循环，因为这意味着数组已经是排序状态。

main 函数

  • 初始化并赋值一个vector<int>类型的数组arr。
  • 调用bubbleSort函数对数组进行排序。
  • 遍历并打印排序后的数组，展示排序结果。

冒泡排序的特点和性能

  • 简单直观：冒泡排序的算法逻辑简单，容易实现。
  • 时间复杂度：平均和最坏的情况下都是O(n^2)，其中n是数组长度。最好的情况（已经是排序状态的数组）下，由于提前终止的优化，时间复杂度是O(n)。
  • 空间复杂度：O(1)，冒泡排序是一个原地排序算法，不需要额外的存储空间。
  • 稳定性：冒泡排序是稳定的，因为相等的元素不会交换顺序。
  • 适用性：由于其较高的时间复杂度，在处理大数据集时可能不是最优选择，但对于小数据集或基本有序的数据集，冒泡排序可以非常高效。

这段代码通过在每轮遍历后判断是否进行了元素交换，从而可能在完成所有排序前提前结束，这是一个对冒泡排序常见的优化手段，可以在最好的情况下提升性能。

选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的基本思想是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的元素中选出最小（或最大）的一个，放到已排序序列的末尾，以此类推，直到全部待排序的数据元素排完。

  • 选择排序的步骤：
  1. 在未排序序列中找到最小（最大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（最大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

  • 选择排序的特点：

  • 时间复杂度：不管数组的排列如何，选择排序的时间复杂度总是O(n^2)，其中n是数组的长度。这是因为选择排序每次找最小元素需要遍历整个未排序的部分。

  • 空间复杂度：O(1)，是一种原地排序算法。

  • 稳定性：选择排序是不稳定的排序算法，因为它会跳跃式地交换数据项的位置。

  • 适用性：由于其O(n^2)的时间复杂度，它不适合于数据量大的排序应用。

下面是选择排序的C++实现：

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        // 找到最小元素的索引
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小元素到当前位置
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);

    cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

在这段代码中，selectionSort函数通过两层循环实现排序逻辑。外层循环遍历数组元素，内层循环寻找未排序部分的最小元素。当内层循环完成后，将找到的最小元素与外层循环的当前元素进行交换。这样，每次外层循环迭代都会将未排序部分的最小元素放到已排序部分的末尾，直至排序完成。

这段代码演示了选择排序算法的C++实现。选择排序是通过重复找出数组中的最小元素，并将它放到数组的开始位置，从而达到排序的目的。以下是对这个过程的详细分析：

selectionSort(vector<int>& arr)函数

  • 参数：arr，一个引用传递的整数vector，表示待排序的数组。

  • 过程：

    • 外层循环：从0到n-2遍历数组。变量i标识了当前排序过程的开始位置，也即是已排序部分与未排序部分的分界线。
      • 最小元素索引：minIndex用于跟踪每次内层循环中找到的最小元素的索引。每次外层循环开始时，将minIndex初始化为当前外层循环的索引i。
    • 内层循环：从i+1到n-1遍历数组，寻找未排序部分的最小元素。如果发现比arr[minIndex]更小的元素，就更新minIndex为该元素的索引。
    • 交换元素：内层循环结束后，如果minIndex不等于i（意味着找到了比arr[i]更小的元素），则将arr[i]和arr[minIndex]的位置交换。这样确保了arr[i]是从i到数组末尾元素中的最小值。

选择排序的特性和性能

  • 简单直观：选择排序算法易于理解和实现。
  • 时间复杂度：对于包含n个元素的数组，选择排序需要进行n-1次外层循环，每次循环中又需要进行最多n-1次比较（随着排序的进行，比较次数逐渐减少）。因此，总的时间复杂度是O(n^2)。
  • 空间复杂度：O(1)，选择排序是一个原地排序算法，不需要额外的存储空间。
  • 稳定性：选择排序是不稳定的排序算法。交换操作可能会改变相等元素的初始相对顺序。
  • 适用性：由于其较高的时间复杂度，选择排序不适合于数据量大的排序应用，但它适用于小数据集或者排序操作的开销比交换操作小得多的场景。

215. 数组中的第K个最大元素

#include <iostream>
#include <vector>
// #include <algorithm>

class Solution {
public:
    int partition(std::vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] >= pivot) {
                std::swap(nums[i] , nums[j]);
                i++;
            }
        }
        std::swap(nums[i], nums[right]);
        return i;
    }

    int quickSelect(std::vector<int>& nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int pivotIndex = partition(nums, left, right);
        if (k == pivotIndex) return nums[k];
        else if (k < pivotIndex) return quickSelect(nums, left, pivotIndex - 1, k);
        else return quickSelect(nums, pivotIndex + 1, right, k);
    }

    int findKthLargest(std::vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k - 1);
    }
};

int main() {
    Solution solution;

    // 示例 1
    std::vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    int k1 = 2;
    std::cout << "Example 1: " << solution.findKthLargest(nums1, k1) << std::endl; // 应输出: 5

    // 示例 2
    std::vector<int> nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    int k2 = 4;
    std::cout << "Example 2: " << solution.findKthLargest(nums2, k2) << std::endl; // 应输出: 4

    // 更多测试
    std::vector<int> nums3 = {2, 1};
    int k3 = 2;
    std::cout << "More Test: " << solution.findKthLargest(nums3, k3) << std::endl; // 应输出: 1

    return 0;
}

347. 前 K 个高频元素

补充：

小顶堆（最小堆）和大顶堆（最大堆）

小顶堆（最小堆）和大顶堆（最大堆）是二叉堆的两种形式，都是完全二叉树。它们的主要区别在于节点元素的排列顺序，这影响了堆操作的行为，尤其是元素的添加、移除和访问顶部元素时的行为。

  • 小顶堆（最小堆）

  • 定义：在小顶堆中，任何一个父节点的值都小于或等于它的子节点的值。

  • 顶部元素：堆顶（根节点）是所有元素中的最小值。

  • 操作特性：当你从小顶堆中移除元素时，你总是移除当前的最小元素。当你添加一个新元素到小顶堆时，堆会重新调整，确保新的根节点依然是最小元素。

  • 用途：小顶堆通常用于实现优先队列，优先处理值最小的元素。例如，在Dijkstra的最短路径算法中，小顶堆用于持续地访问最小的边权重。

  • 大顶堆（最大堆）

  • 定义：在大顶堆中，任何一个父节点的值都大于或等于它的子节点的值。

  • 顶部元素：堆顶（根节点）是所有元素中的最大值。

  • 操作特性：当你从大顶堆中移除元素时，你总是移除当前的最大元素。当你添加一个新元素到大顶堆时，堆会重新调整，确保新的根节点依然是最大元素。

  • 用途：大顶堆通常用于排序算法（如堆排序），以及在需要快速访问最大元素的场景中，例如，任务调度中优先执行最重要（或最紧急）的任务。

小顶堆和大顶堆的主要区别在于它们如何组织数据。小顶堆让最小元素易于访问，而大顶堆让最大元素易于访问。选择使用哪一种类型的堆取决于具体的应用场景和需要优先访问的元素类型（最大或最小）。在实际应用中，通过调整比较逻辑，同一个数据结构（如优先队列）可以实现小顶堆或大顶堆的行为。

一个有效的方法是使用哈希表和堆（优先队列）。

思路分析：

  1. 使用哈希表统计每个元素的频率：这一步是O(n)的时间复杂度，n是数组nums的大小。

  2. 使用最小堆（优先队列）来维护频率最高的k个元素：这里的关键在于堆的大小保持为k，这样，当遍历完所有元素后，堆中就是频率最高的k个元素。由于每次插入操作的时间复杂度是O(log k)，整体复杂度为O(n log k)，这满足了题目要求。

    #include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <utility> // For pair

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 使用哈希表统计每个元素的频率
        unordered_map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
        }

        // 定义一个最小堆，来维护频率最高的k个元素
        // 堆中的元素是一个pair，包含元素值和其频率
        auto compare = [&frequencyMap](int num1, int num2) {
            return frequencyMap[num1] > frequencyMap[num2];
        };
        priority_queue<int, vector<int>, decltype(compare)> minHeap(compare);

        // 遍历哈希表，维护大小为k的堆
        for (auto& entry : frequencyMap) {
            minHeap.push(entry.first);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // 将堆中的元素放入结果数组
        vector<int> topK;
        while (!minHeap.empty()) {
            topK.push_back(minHeap.top());
            minHeap.pop();
        }

        return topK;
    }
};

int main() {
    Solution solution;
    vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    int k1 = 2;
    vector<int> result1 = solution.topKFrequent(nums1, k1);
    cout << "Example 1: ";
    for (int num : result1) {
        cout << num << " ";
    }
    cout << endl;

    vector<int> nums2 = {1};
    int k2 = 1;
    vector<int> result2 = solution.topKFrequent(nums2, k2);
    cout << "Example 2: ";
    for (int num : result2) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
阅读全部

相关推荐

  1. 排序算法笔记

    2024-04-01 06:08:06       37 阅读

  5. 算法笔记：全排列

    2024-04-01 06:08:06       53 阅读

  6. 算法笔记p142快速排序

    2024-04-01 06:08:06       41 阅读

  7. 算法笔记p414拓扑排序

    2024-04-01 06:08:06       47 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-01 06:08:06       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-01 06:08:06       100 阅读

  9. 在Django里面运行非项目文件

    2024-04-01 06:08:06       82 阅读

  19. Python语言-面向对象

    2024-04-01 06:08:06       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-01 06:08:06       85 阅读

热门阅读

  3. 文件系统 FTP Ubuntu 安装入门介绍

    2024-04-01 06:08:06       47 阅读

  4. SOA、分布式、微服务之间的关系？

    2024-04-01 06:08:06       42 阅读

  10. 深入探索语言模型：原理、应用与评估

    2024-04-01 06:08:06       40 阅读

  16. 设计模式(11)：适配器模式

    2024-04-01 06:08:06       44 阅读

  18. 2024.2.1力扣每日一题——数字游戏

    2024-04-01 06:08:06       35 阅读

  24. 深入探索前端与后端数据交互：打造稳健、高效的数据通道

    2024-04-01 06:08:06       37 阅读

  28. Vue企业级项目开发axios

    2024-04-01 06:08:06       43 阅读

  30. 微信小程序——小程序和页面生命周期详解

    2024-04-01 06:08:06       43 阅读