【基础算法】1.基础习题课1

[toc]

系列文章

【基础算法】1.排序及二分

【基础算法】2.高精度&前缀和与差分

【基础算法】3.双指针、位运算、离散化、区间合并

【数据结构】1.链表

【基础算法】习题课1

系列代码

GALA-Lin/Algorithm: CSDN基础算法系列配套代码

题解

1. 第K个数（AC786）

题目描述：
给定一个整数序列，要求出第K大的数。

解法分析：
本题可以使用两种方法来求解：

• 解法一：全排序
  将整个数组进行排序，然后直接访问排序后的位置，返回第K个数。这种方法简单明了，但时间复杂度为 (O(n \log n))。

• 解法二：快速选择算法
  使用快速选择算法，只关注与第K个数相关的部分，时间复杂度为 (O(n))。该方法通过选择一个pivot（基准元素）来划分数组，然后递归地在左边或右边进行操作，直到找到目标位置。

int partition(int a[], int left, int right, int pivot);
int quickSelect(int a[], int left, int right, int k);

在这里，首先根据基准值将数组分隔，再根据基准值的位置决定下一步递归的方向，最终达到找到第K个数的目的。

2. 立方根（AC790）

题目描述：
求一个数的立方根。

解法分析：
本题提供了两种解法：

• 解法一：利用库函数
  使用pow函数或cbrt函数计算立方根，这是最简单的方法。

• 解法二：二分查找
  采用二分查找的方式，设定左右边界，逐步缩小范围直到找到立方根。精度控制在 (1e-8)。

while (right - left > 1e-8) {
    mid = (left + right) / 2;
    if (mid * mid * mid - x < 0) {
        left = mid;
    } else {
        right = mid;
    }
}

通过不断调整左右区间和判断条件逼近真实值，最终输出求得的立方根。

3. 逆序对（AC788）

题目描述：
给定一个整数数组，求出数组中形成的逆序对的数量。逆序对是指：对于数组中的两个索引 (i) 和 (j) ，如果 (i < j) 并且 (nums[i] > nums[j])，那么这对索引称为一个逆序对。

解法分析：
本题有两种解决方案：

• 解法一：双指针
  利用双层循环的方法，遍历每个元素，并统计在该元素前面有多少个元素是比它大的。具体步骤如下：

1. 外层循环遍历每个元素 (nums[i])。
2. 内层循环从 (i+1) 开始遍历到数组末尾，统计比 (nums[i]) 大的元素数量。
3. 每次发现一个比当前元素大的元素，就增加逆序对计数。

这种方法简单易懂，但由于存在双重循环，所以时间复杂度为 (O(n^2))，在数据规模较大时，性能会较差。

int inversePairs(vector<int>& nums) {
    int n = nums.size();
    vector<int> count(n + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] > nums[j]) {
                count[i]++;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += count[i];
    }
    return ans;
}

• 解法二：归并排序和计数

此解法使用归并排序的思想来解决问题，并且在归并的过程中计算逆序对。具体步骤如下：

1. 递归分解：
   使用归并排序的递归方式，将数组分解为两个子数组，直到每个子数组的大小为1。

2. 合并并计数：
   在合并两个排序好的子数组时，如果发现左边的元素大于右边的元素，这意味着左边的这个元素及其后面的所有元素都构成了逆序对。因此，可以通过当前左边的索引与右边的索引确定逆序对的数量。

   具体来说，当左边数组的元素 (nums[i]) 大于右边数组的元素 (nums[j]) 时，左边当前的元素与右边剩余元素均构成逆序对，即有 (mid - i + 1) 个逆序对。

3. 更新逆序对计数：
   创建一个计数数组，存储每个元素在合并时统计的逆序对数量。最终将所有逆序对数量累加得到结果。

此方法的时间复杂度为 (O(n \log n))，效率显著提升，适合处理大规模数据。

void mergeSort(vector<int>& nums, int left, int right, vector<int>& count) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid, count);
        mergeSort(nums, mid + 1, right, count);
        merge(nums, left, mid, right, count);
    }
}

void merge(vector<int>& nums, int left, int mid, int right, vector<int>& count) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            // 统计逆序对
            count += (mid - i + 1);
        }
    }
    
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    
    for (int i = left; i <= right; i++) {
        nums[i] = temp[i - left];
    }
}

总结

这三个问题分别利用了排序、查找和统计的算法。通过不同的处理方法，我们能够在算法设计中选择最优解，并且合理调整数据结构和算法复杂度来满足不同数据规模下的需求。