统计数组中出现了K次的数

题目：一个数组中一种数出现了 $K$ 次，其他数都出现了 $M$ 次（$M>1$，$K<M$），找出出现了 $K$ 次的数，如果这种数出现的次数不是 $K$ 次，则返回 -1。

要求：额外空间复杂度为 $O(1)$，时间复杂度为 $O(n)$

思路：任何形式的数都能转化成数组形式的二进制，申请一个固定数组 int t[32]，每个数字的二进制位的 1 累加到 t 中，通过 t 中每个元素是否为 $M$ 的整数倍而确定初选了 $K$ 次的数的每个二进制位。

代码：

/*************************************************************************
	> File Name: 004.统计数组中出现了K次的数.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  5/ 2 13:35:38 2022
 ************************************************************************/

#include <iostream>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
using namespace std;

//找到arr数组中出现k次的这种数，其他数都出现m次
//如果这种数出现的次数不是k次，则返回-1
int onlyKTimes(vector<int> &arr, int k, int m) {
    int t[32] = {0};
    //t[0]:0位置的1出现的次数
    //t[i]:i位置的1出现的次数

    for (int num : arr) {
        for (int i = 0; i < 32; i++) {
            t[i] += ((num >> i) & 1);

            /*
            if (((num >> i) & 1) != 0) {//num的第i位为1
                t[i]++;
            }
            */
        }
    }

    int ans = 0;
    for (int i = 0; i < 32; i++) {
        if (t[i] % m == 0) { //待找的数的第i位为0
            continue;
        }
        if (t[i] % m == k) {
            ans |= (1 << i);
        } else { //待找的数出现次数不是k次
            return -1;
        }
    }

    //特例：0出现的次数不是k次的时候，会直接返回0，而不是-1, 所以需要再统计0出现的次数
    if (ans == 0) {
        int cnt = 0;
        for (int num : arr) {
            if (num == 0) cnt++;
        }

        if (cnt != k) return -1;
    }

    return ans;
}


int test(vector<int> &arr, int k, int m) {
    unordered_map<int, int> map;

    for (int num : arr) {
        if (map.count(num)) {
            map[num]++; 
        } else {
            map[num] = 1;
        }
    }

    for (int num : arr) {
        if (map[num] == k)
            return num;
    }


    return -1;
}

//[-range, range]
int randomNumber(int range) {
    return ((rand() % range) + 1) - ((rand() % range) + 1);
}

vector<int> randomArray(int maxKinds, int range, int k, int m) {
    //出现k次的数
    int kTimeNum = randomNumber(range);

    //出现k次的数实际出现的次数
    double decide = (rand() % 101) / (double)101;
    int times = decide < 0.5 ? k : (rand() % (m - 1)) + 1;


    //数组所有数字的种类
    int numKinds = (rand() % maxKinds) + 2;

    vector<int> arr(times + (numKinds - 1) * m);

    int index = 0;

    //将出现k次的数填入arr中
    for (; index < times; index++) {
        arr[index] = kTimeNum;
    }
    //数组中数的种类-1
    numKinds--;

    unordered_set<int> set;
    set.insert(kTimeNum);

    //给arr填值
    while (numKinds != 0) {
        int curNum = 0;
        do {
            curNum = randomNumber(range);
        } while (set.count(curNum));

        set.insert(curNum);
        numKinds--;
        for (int i = 0; i < m; i++) {
            arr[index++] = curNum;
        }
    }

    //打乱arr
    for (int i = 0; i < arr.size(); i++) {
        int j = rand() % (arr.size());
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    return arr;
}


void printArray(vector<int> &arr) {
    if (arr.size() == 0) return ;
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    srand(time(0));
    int kinds = 10; //数字种类
    int range = 200; //数字范围
    int testTime = 10001;
    int maxVal = 9; //最大值

    cout << "Test begin:" << endl;
    for (int i = 0; i < testTime; i++) {
        int a = (rand() % maxVal) + 1; //[1, 9];
        int b = (rand() % maxVal) + 1;
        int k = min(a, b);
        int m = max(a, b);

        if (k == m) m++; //保证k < m

        vector<int> arr = randomArray(kinds, range, k, m);
        
        int ans1 = test(arr, k, m);
        int ans2 = onlyKTimes(arr, k, m);
        if (ans1 != ans2) {
            cout << "Oops!" << endl;
            printArray(arr);
            cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << endl;
            break;
        }

        if (i && i % 100 == 0) cout << i << "cases passed" << endl;
    }

    cout << "Test end!" << endl;

    return 0;
}

最后

以上就是迷路故事为你收集整理的统计数组中出现了K次的数的全部内容，希望文章能够帮你解决统计数组中出现了K次的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。