数据结构与算法再探（七）查找-排序

news/2025/2/24 17:45:09

查找

一、二分查找

二分查找是一种高效的查找算法，适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。

二分查找关键点

不变量

在二分查找中，不变量是指在每一步迭代中保持不变的条件。对于二分查找来说，不变量通常是：目标值在当前搜索范围内：在每次迭代中目标值始终位于 left 和 right 指针之间。如在查找一个值 target并且当前的搜索范围是 arr[left]- arr[right]，那么我们可以保证如果 arr[left]≤target≤arr[right]，则 target 一定在这个范围内。

区间定义

二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，二分查找中的左闭右开和左闭右闭的本质区别主要体现在搜索范围的定义和边界处理上。这种选择会影响算法的实现细节、边界条件的处理以及最终的查找结果。

二分查找实现

1）左闭右闭区间 [left, right]

定义：left 和 right 都是闭合的，表示搜索范围包括 left 和 right。当 left 等于 right 时，搜索范围仍然包含 right。在计算中间值时，使用 mid = left + (right - left) / 2。但是：这种都是闭区间可能会导致重复元素的处理变得复杂，特别是在查找第一个或最后一个出现的元素时。

int binarySearchClosed(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            left = mid + 1; // 在右半部分继续查找
        } else {
            right = mid - 1; // 在左半部分继续查找
        }
    }

    return -1; // 未找到目标值
}
2）左闭右开区间 [left, right)

left 是闭合的，right 是开合的，表示搜索范围包括 left，但不包括 right。当 left 等于 right 时，搜索范围不包含 right，因此 right 的值是 arr.size()。并且在更新 right 时使用 right = mid。优点：避免了中间元素重复的情况，特别适合查找插入位置。逻辑上更容易处理边界条件，特别是在处理空数组或查找插入位置时。但是没有左闭右闭直观。

int binarySearchOpen(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size(); // 注意这里是 arr.size()

    while (left < right) { // 注意这里是 left < right
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            left = mid + 1; // 在右半部分继续查找
        } else {
            right = mid; // 在左半部分继续查找
        }
    }

    return -1; // 未找到目标值
}

二分区间查找

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target的下标 i
    // 如果数组为空，或者所有数都 <target，则返回nums.size()
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int) nums.size() - 1; // 闭区间
        while (left <= right) {
            // 循环不变量：nums[left-1] < target   nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; 
            } else {
               left = mid + 1; 
            }
        }
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

 

二、深度搜索

沿分支尽可能深入，到达叶子节点后回溯，继续探索其他分支。

113. 路径总和 II - 力扣（LeetCode）

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def dfs(node, path, current_sum):
            if not node:
                return
            current_sum += node.val
            path.append(node.val)
            if not node.left and not node.right and current_sum == targetSum:
                result.append(list(path))
            dfs(node.left, path, current_sum)
            dfs(node.right, path, current_sum)
            path.pop()  # 回溯
        result = []
        dfs(root, [], 0)
        return result

三、广度搜索

按层级逐层遍历，先处理离根节点最近的节点，可以使用队列（FIFO）存储待访问节点。

102. 二叉树的层序遍历 - 力扣（LeetCode）

BFS层次遍历

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans=[]
        q=deque([root])
        while q:
            vals=[]
            for _ in range(len(q)):
                node=q.popleft()
                vals.append(node.val)
                if node.left: q.append(node.left)
                if node.right:q.append(node.right)
            ans.append(vals)
        return ans

200. 岛屿数量 - 力扣（LeetCode） 

BFS

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    from collections import deque
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                queue = deque([(i, j)])
                grid[i][j] = '0'  # 标记为已访问
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            grid[nx][ny] = '0'
                count += 1
    return count

DFS

def numIslands(grid):
    def dfs(x, y):
        if 0 <= x < rows and 0 <= y < cols and grid[x][y] == '1':
            grid[x][y] = '0'
            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)
    
    rows = len(grid)
    if rows == 0:
        return 0
    cols = len(grid[0])
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

排序

排序算法总结-CSDN博客

数组中第K大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

要在时间复杂度为O(n) 的情况下找到数组中第k个最大的元素，可以使用快速选择（Quickselect）算法。这个算法的思想与快速排序相似，但它只关注找到第k 个最大的元素，而不是对整个数组进行排序。（排序后return nums[nums.size() - k];  O(nlogn)）

选择基准元素：从数组中随机选择一个基准元素。（快排一趟确定一个元素的位置）
分区操作：将数组分为两部分，左侧是小于基准的元素，右侧是大于基准的元素。
判断基准位置：如果基准元素的位置正好是n−k（因为我们需要找到第k 个最大的元素），那么这个元素就是我们要找的元素。如果基准元素的位置大于n−k，则第k 个最大的元素在左侧部分。
如果基准元素的位置小于n−k，则第k 个最大的元素在右侧部分。

class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};


http://www.niftyadmin.cn/n/5864664.html

相关文章

Day9，Hot100（图论）

Day9，Hot100（图论）

图论 图论部分推荐 acm 模式&#xff0c;因为图的输入处理不一样 DFS&#xff0c;类似二叉树的递归遍历 BFS&#xff0c;类似二叉树的层次遍历 208. 实现 Trie (前缀树) 数据结构大概如下&#xff1a; 可以看成是 二十六叉树 &#xff08;因为26个小写字母&#xff09; …
阅读更多...
C++的设计模式

C++的设计模式

1. 创建型模式 单例模式 (Singleton) 意图&#xff1a;确保类仅有一个实例&#xff0c;并提供全局访问点。&#xff08;常见的日志类&#xff09;实现&#xff1a;class Singleton { private:static Singleton* instance;Singleton() {} // 私有构造函数 public:static Singl…
阅读更多...
【深度学习】手写数字识别任务

【深度学习】手写数字识别任务

数字识别是计算机从纸质文档、照片或其他来源接收、理解并识别可读的数字的能力&#xff0c;目前比较受关注的是手写数字识别。手写数字识别是一个典型的图像分类问题&#xff0c;已经被广泛应用于汇款单号识别、手写邮政编码识别等领域&#xff0c;大大缩短了业务处理时间&…
阅读更多...
Linux 命令大全完整版（11）

Linux 命令大全完整版（11）

5.文件管理命令 diff&#xff08;differential&#xff09; 功能说明&#xff1a;比较文件的差异。语　　法&#xff1a;diff [-abBcdefHilnNpPqrstTuvwy][-<行数>][-C <行数>][-D <巨集名称>][-I <字符或字符串>][-S <文件>][-W <宽度>…
阅读更多...
DeepSeek本地搭建 和 Android

DeepSeek本地搭建 和 Android

DeepSeek 搭建和 Android 文章目录 DeepSeek 搭建和 Android一、前言二、DeepSeek 本地环境ollama搭建1、软件下载网址&#xff1a;2、Ollama的安装3、配置算法模型和使用qwen2 模型使用&#xff0c; 三、Android Studio 和 DeepSeek四、其他1、Deepseek 使用小结(1) 网页版本可…
阅读更多...
通俗理解Test time Scaling Law、RL Scaling Law和预训练Scaling Law

通俗理解Test time Scaling Law、RL Scaling Law和预训练Scaling Law

一、Scaling Law解释 1、预训练阶段的Scaling Law&#xff08;打地基阶段&#xff09; 通俗解释&#xff1a;就像建房子时&#xff0c;地基越大、材料越多、施工时间越长&#xff0c;房子就能盖得越高越稳。 核心&#xff1a;通过堆资源&#xff08;算力、数据、模型参数&am…
阅读更多...
Express + MongoDB 实现在筛选时间段中用户名的模糊查询

Express + MongoDB 实现在筛选时间段中用户名的模糊查询

使用 $gte&#xff08;大于等于&#xff09;和 $lte&#xff08;小于等于&#xff09;操作符构建时间段查询条件。使用 $regex 操作符进行模糊查询&#xff0c;$options: i 表示不区分大小写。使用 $and 操作符将它们组合起来。 // 处理查询的路由app.get("/users",…
阅读更多...
[设计模式] Builder 建造者模式

[设计模式] Builder 建造者模式

目录 意图 问题 解决 Applying the Builder pattern 主管 结构 伪代码 生成器模式适合应用场景 实现方法 生成器模式优缺点 与其他模式的关系 C代码 main.cc&#xff1a;概念示例 Output.txt&#xff1a;执行结果 意图 Builder 是一种创建性设计模式&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023