劍指offer之找出數(shù)組中重復(fù)數(shù)字

1 問題

給的N個(gè)數(shù)字的數(shù)組，每個(gè)元素的大小范圍大于等于0小于N(0 << a[i] < N),找出數(shù)組中有哪些數(shù)字重復(fù)了并且這個(gè)數(shù)字重復(fù)了多少次，一共有幾個(gè)數(shù)字重復(fù)了。

 
2思路

由于元素的大小范圍大于等于0小于N(0 << a[i] < N),我們直接把這個(gè)元素的大小作為下標(biāo)(不會(huì)小標(biāo)越界)，每出現(xiàn)一次就是把這個(gè)元素的大小作為下標(biāo)的值進(jìn)行增加1，然后最后去判斷新數(shù)組的值是否大于1


 
3 代碼實(shí)現(xiàn)

    #include <iostream>
    #include <stdlib.h>
     
    using namespace std;
     
    int main()
    {
        std::cout << "請(qǐng)輸入N個(gè)數(shù)字" << std::endl;
        int n = 0;
        std::cin >> n;
        std::cout << std::endl;
        if (n <= 0) {
            std::cout << "輸入的數(shù)字錯(cuò)誤" << std::endl;
            return -1;
        }
        int *a = new int[n];
        //初始化數(shù)組
        memset(a, 0, n * sizeof(int));
        std::cout << "分別輸入每個(gè)數(shù)字的值" << std::endl;
        for (int i = 0; i < n; ++i)
        {
            int num = 0;
            std::cin >> num;
            if (num < 0 || num >= n)
            {
                std::cout << "輸入的數(shù)字值" << a[i] << "不對(duì)" << std::endl;
                return -1;
            }
            a[num]++;
        }
        int count = 0;
        for (int i = 0; i < n; ++i)
        {
            if (a[i] > 1)
            {
                ++count;
                std::cout << "數(shù)字" << i << "重復(fù)" << a[i] << "次" << std::endl;
            }
        }
        std::cout << "總共重復(fù)的數(shù)字有" << count << "個(gè)" << std::endl;
        delete[] a;
        return 0;
    }


 
4 運(yùn)行結(jié)果

    請(qǐng)輸入N個(gè)數(shù)字
    15
     
    分別輸入每個(gè)數(shù)字的值
    2
    3
    4
    5
    4
    3
    2
    2
    3
    5
    5
    5
    5
    6
    6
    數(shù)字2重復(fù)3次
    數(shù)字3重復(fù)3次
    數(shù)字4重復(fù)2次
    數(shù)字5重復(fù)5次
    數(shù)字6重復(fù)2次
    總共重復(fù)的數(shù)字有5個(gè)


5 總結(jié)

我們要記得把值作為數(shù)組下標(biāo)的方法（前提不會(huì)下標(biāo)越界），然后在C和C++中如果要有動(dòng)態(tài)數(shù)組，我們需要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};

不然編譯會(huì)提示如下

variable-sized object may not be initialized

但是在java里面是可以這樣寫的，要注意。

 



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)