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

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/85967756