剑指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里面是可以这样写的，要注意。