C++之《剑指offer》学习记录（7）：不修改数组找出重复的数字

时间：2024-10-21 20:25:54

笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：不修改数组找出重复的数字

题设：

不修改数组找出重复的数字。
在一个长度为n+1的数组里所有的数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

这道题和“数组中重复的数字”非常像，但是多加了一个限制：不能修改数组。

测试用例

  1. 符合要求的用例：{1,2,3,4,5,5},{1,3,4,5,2,2,3}
  2. 数字范围超过n+1的用例：{1,7,8,9,7}
  3. 输入为空：{}
  4. 没有重复数字：{1,2,3,5,4}

解法一：哈希

这个解法不会修改输入的数组，时间复杂度是O(n)，空间复杂度也是O(n)。

int getDuplicate(vector<int> &nums)
{
    if (nums.size() <= 0)
    {
        return -1;
    }
    for (auto num : nums)
    {
        if (num >= nums.size())
        {
            return -1;
        }
    }
    // 通过unordered_set实现
    unordered_set<int> un_set;
    for (auto num : nums)
    {
        if (un_set.find(num) != un_set.end())
        {
            return num;
        }
        un_set.insert(num);
    }
    return -1;
}

解法二：基于二分查找

这个方法是“用时间换空间”，时间复杂度为O(nlogn)，空间复杂度为O(1)

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int getCount(vector<int> &nums, int start, int end)
{
    if (nums.size() <= 0)
    {
        return 0;
    }
    int count = 0;
    for (auto num : nums)
    {
        if (num >= start && num <= end)
        {
            count++;
        }
    }
    return count;
}

int getDuplicate(vector<int> &nums)
{
    if (nums.size() <= 0)
    {
        return -1;
    }
    for (auto num : nums)
    {
        if (num >= nums.size())
        {
            return -1;
        }
    }

    int start = 1;
    int end = nums.size() - 1;
    int middle = (start + end) / 2;
    int count;

    while (end >= start)
    {
        count = getCount(nums, start, middle);
        if (count > middle - start + 1)
        {
            end = middle;
            if (start == end)
            {
                return start;
            }
        }
        else
        {
            start = middle + 1;
            if (start == end)
            {
                return start;
            }
        }
        middle = (start + end) / 2;
    }

    return -1;
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {2, 2, 2, 2, 5, 5};
    // vector<int> nums = {1, 7, 8, 9, 7};
    // vector<int> nums = {};
    // vector<int> nums = {1, 2, 3, 5, 4};
    cout << getDuplicate(nums) << endl;
    return 0;
}

以上代码按照二分查找的思路来完成，如果输入数组长度为n，则函数getCount就要被调用O(logn)次，每次调用需要O(n)的时间，所以总的时间复杂度为O(nlogn)；由于没有使用辅助数组，该代码空间复杂度为O(n)。
这个方法的主要思路就是在数组长度为n+1，数组内数的范围是1~n的前提下，数组中肯定是有重复的元素的。二分法不是对数组本身进行二分法，而是对1~n这n个数进行二分法操作。
假如有数组{3,2,2,1,4,5}，这里一共有6个数，数组元素的范围在1~5之间，则中间元素就是3，先统计1~3在数组中出现的总次数，有4次，这说明肯定有一个数是重复的。这使基于1~3，在求中间元素就是2，统计1~2在数组中出现的次数，有3次，这说明在这个区间肯定有一个数是重复的。基于1~2，求中间元素值就是1，统计1在数组中出现的次数，只有1次，这时就可以说明重复的元素是2。

相关文章