剑指Offer：算法题解与代码

"剑指offer.md" 这篇资源是关于《剑指Offer》这本书中的算法题目的编程实现，主要语言是C++，涉及的标签包括算法和C++。作者使用Markdown格式编写了文档，使得排版清晰，便于阅读。文件中包含的具体题目有二维数组的查找和数组中重复的数字。 首先，我们来看第一个题目——二维数组的查找。这个问题要求在一个特殊的二维数组中查找特定的整数，这个数组的特殊之处在于每行都是递增排序，每列也是递增排序。解决这个问题，我们可以采用逐行扫描的方法，先确定目标整数可能存在的行，然后在这一行中使用二分查找法来快速定位目标。代码中的`binary_search`函数就是用来执行二分查找的，它会检查目标整数是否在给定的有序数组范围内。如果找到，返回true，否则返回false。 ```cpp class Solution { public: bool Find(int target, vector<vector<int>> array) { int xLen = array.size(); if (xLen <= 0) { return false; } int yLen = array[0].size(); if (yLen <= 0) { return false; } bool flag = false; for (int i = 0; i < xLen; i++) { // 在当前行查找 if (array[i].at(0) <= target && target <= array[i].at(yLen - 1)) { // 找到 if (binary_search(array[i].begin(), array[i].end(), target)) { flag = true; break; } } } return flag; } }; ``` 接下来是第二个题目——数组中重复的数字。给定一个长度为n的数组，数组中的元素值在0到n-1之间，并且存在重复数字。任务是找出数组中任意一个重复的数字。这里可以使用一种叫做“快慢指针”或者“龟兔赛跑”的方法来解决。由于数组中的元素值范围是0到n-1，我们可以创建一个大小为n的新数组，用新数组的下标表示原数组中的元素，值表示新数组中对应位置的元素出现的次数。当我们在新数组中遍历时，如果遇到某个位置的值大于1，说明找到了重复的数字。代码如下： ```cpp class Solution { public: int findDuplicate(vector<int>& numbers) { int n = numbers.size(); vector<int> count(n, 0); for (int num : numbers) { if (count[num] == 1) { return num; } count[num]++; } throw "No duplicate found!"; } }; ``` 在这个解决方案中，我们通过遍历原数组，将每个元素作为索引去更新新数组的计数。当遇到计数值为1时，意味着这是第一次遇到该数字，将其计数加1；如果遇到计数值已经是1，说明之前已经遇到过这个数字，此时返回这个数字即可。 这两个问题都是《剑指Offer》中的经典算法题，旨在考察对数据结构和算法的理解与应用能力，对于准备面试或提升编程技能的程序员来说是非常有价值的练习。通过解决这些问题，可以加深对二分查找、数组操作以及查找算法的理解，同时锻炼编程技巧和解决问题的能力。