剑指offer之找出数组中重复数字

1 问题

给的N个数字的数组，每个元素的大小范围大于等于0小于N(0 << a[i] < N),找出数组中有哪些数字重复了并且这个数字重复了多少次，一共有几个数字重复了。

 
2思路

由于元素的大小范围大于等于0小于N(0 << a[i] < N),我们直接把这个元素的大小作为下标(不会小标越界)，每出现一次就是把这个元素的大小作为下标的值进行增加1，然后最后去判断新数组的值是否大于1


 
3 代码实现

    #include <iostream>
    #include <stdlib.h>
     
    using namespace std;
     
    int main()
    {
        std::cout << "请输入N个数字" << std::endl;
        int n = 0;
        std::cin >> n;
        std::cout << std::endl;
        if (n <= 0) {
            std::cout << "输入的数字错误" << std::endl;
            return -1;
        }
        int *a = new int[n];
        //初始化数组
        memset(a, 0, n * sizeof(int));
        std::cout << "分别输入每个数字的值" << std::endl;
        for (int i = 0; i < n; ++i)
        {
            int num = 0;
            std::cin >> num;
            if (num < 0 || num >= n)
            {
                std::cout << "输入的数字值" << a[i] << "不对" << std::endl;
                return -1;
            }
            a[num]++;
        }
        int count = 0;
        for (int i = 0; i < n; ++i)
        {
            if (a[i] > 1)
            {
                ++count;
                std::cout << "数字" << i << "重复" << a[i] << "次" << std::endl;
            }
        }
        std::cout << "总共重复的数字有" << count << "个" << std::endl;
        delete[] a;
        return 0;
    }


 
4 运行结果

    请输入N个数字
    15
     
    分别输入每个数字的值
    2
    3
    4
    5
    4
    3
    2
    2
    3
    5
    5
    5
    5
    6
    6
    数字2重复3次
    数字3重复3次
    数字4重复2次
    数字5重复5次
    数字6重复2次
    总共重复的数字有5个


5 总结

我们要记得把值作为数组下标的方法（前提不会下标越界），然后在C和C++中如果要有动态数组，我们需要new和malloc，我们不能这样写

    nt n = 0;
    scanf("%d\n", &n);
    int a[n] = {0};
     
    int n = 0;
    std::cin >> n >> std::endl;
    int a[n] = {0};

不然编译会提示如下

variable-sized object may not be initialized

但是在java里面是可以这样写的，要注意。

 



 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)