剑指 Offer 03 数组中重复的数字

概述

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

暴力遍历法

首先声明一个布尔数组用以记录，之后直接遍历原数组。

时间复杂度 O(n)，空间复杂度 O(n)。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<bool> flag(nums.size(), false);
        for(int i=0; i<nums.size(); i++) {
            if (flag[nums[i]]) return nums[i];
            flag[nums[i]] = true;
        }
        return 0;
    }
};

暴力遍历法 #2

注意到数字的范围为 0~1，且我们也只需要找出一个即可。 因此可以直接用原数组来进行记录。

时间复杂度 O(n)，空间复杂度 O(1)。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++) {
            if (nums[abs(nums[i])] < 0) return abs(nums[i]);
            nums[abs(nums[i])] *= -1;
        }
        return 0;
    }
};

排序法

对其进行排序后从头开始遍历。

时间复杂度 O(nlogn)，空间复杂度 O(1)。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int last = -1;
        for(auto num : nums) {
            if(num == last) return num;
            last = num;
        }
        return last;
    }
};

Links: sword-offer-03

未经允许，禁止转载，本文源站链接：https://iamazing.cn/