在其它数都出现k次的数组中找到只出现一次的数

[编程题]在其它数都出现k次的数组中找到只出现一次的数

热度指数：1245 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整型数组arr和一个大于1的整数k。已知arr中只有1个数出现了一次，其他的数出现k次，请返回出现了1次的数。

输入描述:

输入包含两行，第一行包含两个整数n和k，1<=n<=10⁵，1 < k <= 100，n代表数组arr的长度，第二行n个整数，代表数组arr，数组arr中每个数都是32位整数。

输出描述:

输出一个整数，代表唯一出现1次的数。

示例1

输入

7 3
5 4 1 1 5 1 5

输出

备注:

时间复杂度,额外空间复杂度。

算法知识视频讲解

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] base = new int[32];
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int[] kBinary = getKBinaryNum(scanner.nextInt(),k);
            baseAdd(base,kBinary,k);
        }
        System.out.print(getResult(base,k));
		
	}
    public static int getResult(int[] base,int k){
        int res = 0;
        int m = 1; 
        for(int i=31;i>=0;i--){
            res += base[i] * m;
            m *= k;
        }
        return res;
    }
    
    
    public static void baseAdd(int[] base,int[] kBinary,int k){
           for(int i=0;i<32;i++){
               base[i] = (base[i]+kBinary[i]) % k;
           }
    }
    
    public static int[] getKBinaryNum(int num,int k){
        int[] arr = new int[32];
        int index = 31;
        while(index>=0){
            arr[index--] = num % k;
            num = num/k;
        }
        return arr;
    }
}

发表于 2019-10-22 13:01:44 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k, x;
    cin>>n>>k;
    int a[32] = {0};
    for(int i=0;i<n;i++){
        cin>>x;
        for(int j=31;j>=0;j--){
            if(x&1)
                a[j]++;
            x >>= 1;
        }
    }
    x = 0;
    for(int i=0;i<32;i++){
        x <<= 1;
        x += a[i]%k;
    }
    cout<<x<<endl;
    return 0;
}

发表于 2020-05-29 11:39:03 回复(0)

华未央

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int k, n, t;
    int xx[32] = { 0 };
    cin >> n >> k;
    vector<int> vec;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        vec.push_back(t);
    }
    
    for (int i = 0; i < n; i++)
    {
        int z = vec[i];
        for (int j = 31; j >= 0; j--)
        {
            if ((z & 1) == 1)
                xx[j]++;
            z >>= 1;
        }
    }
    int a = 0;
    for (int i = 0; i<32; i++)
    {
        a <<= 1;
        a += xx[i] % k;
    }
    cout << a;
    return 0;
}

编辑于 2020-03-16 18:59:31 回复(0)

codewind

#include<iostream>
#include <bits/stdc++.h>
#include<vector>
using namespace std;

int main(void) {
    int n,k;cin>>n>>k;
    map<int,int>a;
    int x;
    for(int i=0;i<n;++i) {
        scanf("%d", &x);
        if(a.count(x)) a[x]++;
        else a[x] = 1;
    }
    for (auto it=a.begin();it!=a.end();++it) {
        if(it->second == 1){
            cout<<it->first<<endl;break;
        }
    }
}

发表于 2020-12-04 17:36:26 回复(0)

gapex

vec视作32 X n的二维0/1矩阵，统计每一列中1的总数，记为cnt
所有数第i位 1的总数要么是k的倍数，要么是k的倍数+1
多出来的1就是只出现一次的那个数贡献的

#include <iostream>
(720)#include <vector>
#include <bitset>

static const unsigned INT_BIN_LEN = sizeof(int) * 8; //int 32bit长
using BinInt = std::bitset<INT_BIN_LEN>; //使用bitset表示一个int对象

int main(){
    //处理输入
    using namespace std;
    int n, k;
    cin >> n >> k;
    vector<BinInt> vec;
    vec.reserve(n);
    while(n--){
        int num;
        cin >> num;
        vec.push_back(BinInt(num));
    }

    BinInt res;
    for(int i = 0; i<32; ++i){
        int cnt = 0;
        for(BinInt &num : vec){
            if(num.test(i)) ++cnt;
        }
        if(cnt % k) res.set(i);
    }
    cout << int(res.to_ulong()) << endl;
    return 0;
}

编辑于 2020-05-19 21:29:13 回复(0)