输入包含两行,第一行包含两个整数n和k,1<=n<=105,1 < k <= 100,n代表数组arr的长度,第二行n个整数,代表数组arr,数组arr中每个数都是32位整数。
输出一个整数,代表唯一出现1次的数。
7 3 5 4 1 1 5 1 5
4
时间复杂度,额外空间复杂度。
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; } }
#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; }
#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; } } }
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; }