剑指offer03

剑指offer03：查找数组中重复的数字

题目描述

       在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

解法一：暴力法(不提倡，提交超时)

//暴力解法(不提倡，费时)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i, j;
        for (i = 0; i<int(nums.size()); i++)
            for (j = i + 1; j<int(nums.size()); j++)
                if (nums[i] == nums[j])
                {
                    cout << nums[i];
                    return nums[i];
                    break;
                }
        return nums[i];
    };
};

解法二：基于C++排序方法：(提倡)

对原来的数组进行排序，然后遍历数组，如果当前元素和下一个元素相同，则返回结果。

class Solution2 {
public:
    int findRepeatNumber(vector<int>& nums) {
        int res;
        //sort的用法:对a从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
        sort(nums.begin(), nums.end());  
        for (int i = 0; i < int(nums.size() - 1); i++) {
            if (nums[i] == nums[i + 1]) {
                res = nums[i];
                cout << res;
                break;
            }
        }
        return res;
    }
};

解法三：基于unordered_map解法

class Solution4 {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int>m;
        for (int i = 0; i<int(nums.size()); i++) {
            //将原数组元素作为key,每出现一次相同的数据就+1直接赋值进去，最后在m中key为数组元素，value为对应的元素出现的次数；
            //用操作符[]访问元素的value，如：m[‘key1’]；访问的得到的是key1对应的value。
            //++运算符的优先级高于关系运算符 >
            if (++m[nums[i]] > 1)
            {
                cout << nums[i];
                return nums[i];
            }
        }
        return 0;
    }
};

解法四：基于unordered_set的方法

/******************************************
底层用hash存储, 插入、查找时间复杂度为O(1)
注意c++中的set是红黑树存储插入、查找时间复杂度为O(logn)
此题解空间复杂度 O(n)
***********************************************/
class Solution3 {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> sets;
        for (int i = 0; i <= int(nums.size()); i++) {
            auto ret = sets.insert(nums[i]);
            if (!ret.second) {
                cout << nums[i];
                return nums[i];
            }
        }
        return -1;
    }
};

解法五：基于布尔数组判重

由于数字范围都在0~n - 1之内，考虑利用一个大小和nums相同的布尔数组记录某个数字是否出现过，
如果当前数字没有出现过（对应flag为false），则将对应flag标记为true；
如果当前数字对应flag为true，说明出现过，将其输出。

/******************************************
底层用hash存储, 插入、查找时间复杂度为O(1)
注意c++中的set是红黑树存储插入、查找时间复杂度为O(logn)
此题解空间复杂度 O(n)
***********************************************/
class Solution5 {
public:
    int findRepeatNumber(vector<int>& nums) {
        //const int size = int(nums.size());
        bool flag[7];
        memset(flag, false, sizeof(flag));
        for (int i = 0; i < int(nums.size()); i++)
            if (flag[nums[i]])
            {
                cout << "重复的数字是: "<<nums[i];
                return nums[i];
            }
            else
                flag[nums[i]] = true;
        return -1;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include<memory>
using namespace std; 

int main()
{
    vector<int> nums = {2,3,1,0,5,2,3};
    Solution5 a;
    a.findRepeatNumber(nums);

    system("pause");
    return 0;
}