C++常见算法题精选与详细讲解

Zhang_Xuu

941人浏览 · 2025-10-10 00:30:00

Zhang_Xuu · 2025-10-10 00:30:00 发布

C++常见算法题精选与详细讲解（含完整注释）

本文精选了几道经典的C++算法题，包括奇偶排序、检测重复元素、查找特殊整数、验证山脉数组、最长连续递增子序列等问题。每道题都配有完整代码、详细注释与思路分析，适合算法初学者入门与复习。

一、按奇偶排序数组

题目描述

给定一个整数数组 nums，要求将数组中的所有偶数排在奇数前面，返回新的数组。

示例

输入：[3,1,2,4]
输出：[2,4,3,1]（偶数在前，奇数在后）

思路分析

这题可以使用双指针法：

左指针 left 负责填偶数；
右指针 right 负责填奇数；
遍历数组，每遇到偶数，就放到 res[left]，每遇到奇数，就放到 res[right]。

这种方法一次遍历即可完成，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。

代码实现

vector<int> sortArrayByParity(vector<int>& nums) {
    int size = nums.size();                // 获取数组大小
    vector<int> res(size, 0);              // 创建结果数组
    int left = 0;                          // 左指针，指向偶数填充位置
    int right = size - 1;                  // 右指针，指向奇数填充位置

    for (int i = 0; i < size; i++) {       // 遍历整个数组
        if (nums[i] % 2 == 0) {            // 如果当前数是偶数
            res[left++] = nums[i];         // 从左侧依次放入
        } else {
            res[right--] = nums[i];        // 从右侧依次放入
        }
    }
    return res;                            // 返回结果数组
}

二、存在重复元素 II

题目描述

给定一个整数数组 nums 和一个整数 k，判断数组中是否存在两个相同的元素，它们的下标之差不超过 k。

示例

输入：nums = [1,2,3,1], k = 3
输出：true

思路分析

这题用滑动窗口 + 哈希表来做最合适：

哈希表 dict 存储窗口内的元素；
每次添加新元素前检查该元素是否已存在；
当窗口大小超过 k 时，删除最早的元素。

代码实现

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> dict;      // 哈希表记录窗口内的元素
    int size = nums.size();

    for (int i = 0; i < size; i++) {
        int num = nums[i];
        if (dict.find(num) != dict.end()) {  // 如果该数已存在
            return true;                     // 存在重复
        }
        dict[num] = 1;                       // 插入当前元素
        if (i >= k)                          // 窗口超过 k
            dict.erase(nums[i - k]);         // 删除最早的一个
    }
    return false;                            // 没找到
}

三、查找出现超过25%的元素

题目描述

已知数组 arr 是按升序排列的，找出出现次数超过数组长度 25% 的元素。

思路分析

设数组长度为 n，那么出现超过 n/4 次的元素，至少有一个满足：
$a rr [i] = a rr [i + n /4]$
因此我们只需从下标 0 到 n/4 遍历一次，检查 arr[i] 和 arr[i + n/4] 是否相等。

代码实现

int findSpecialInteger(vector<int>& arr) {
    int size = arr.size();
    for (int i = 0, j = arr.size() / 4; j < arr.size(); i++, j++) {
        if (arr[i] == arr[j])
            return arr[i];   // 找到超过 25% 的元素
    }
    return 0;                // 没找到（理论上不会出现）
}

四、验证山脉数组

题目描述

给定一个整数数组 arr，判断是否为“山脉数组”。
“山脉数组”定义：

长度至少为 3；
存在一个峰顶 peak；
严格递增到 peak，然后严格递减。

示例

输入：[0,3,2,1]
输出：true

输入：[3,5,5]
输出：false（不能平顶）

代码思路

先从左往右找到峰顶；
再从峰顶往后下降；
必须严格递增后严格递减，不能平或一直增减。

代码实现

bool validMountainArray(vector<int>& arr) {
    int length = arr.size();
    if (length < 3) return false;    // 少于3个元素直接false

    bool inc = false;                // 是否递增过
    bool dec = false;                // 是否递减过
    int i = 1;

    // 第一阶段：递增
    for (; i < length; i++) {
        if (arr[i] == arr[i - 1]) return false; // 平顶
        else if (arr[i] > arr[i - 1]) inc = true;
        else break; // 开始下降
    }

    // 第二阶段：递减
    for (; i < length; i++) {
        if (arr[i] >= arr[i - 1]) return false; // 不能再升
        else dec = true;
    }

    return inc && dec;  // 必须经历上升和下降
}

五、最长连续递增子序列（LCIS）

题目描述

给定一个无序数组 nums，找到其中最长连续递增子序列的长度。

示例

输入：[1,3,5,4,7]
输出：3（最长递增子序列为 [1,3,5]）

思路分析

只要当前元素 nums[i] > nums[i-1]，就说明递增；
否则重置计数；
维护一个全局最大值 l。

代码实现

int findLengthOfLCIS(vector<int>& nums) {
    int a = 1;                 // 当前连续长度
    int l = 1;                 // 最长长度

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) {
            a++;               // 递增，长度+1
        } else {
            a = 1;             // 断开，重置
        }
        l = max(a, l);         // 更新最大值
    }
    return l;
}

总结

题目	思路	时间复杂度	空间复杂度
奇偶排序	双指针	O(n)	O(n)
重复元素检测	哈希表+滑动窗口	O(n)	O(k)
超过25%元素	四分法检测	O(n)	O(1)
山脉数组验证	单次扫描	O(n)	O(1)
最长连续递增子序列	动态计数	O(n)	O(1)