提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 异或运算题
- 体系--01---异或运算
- 需求:
- 一个数组中有一种数出现K次,其他数都出现了M次,M>1,K
异或运算题
体系–01—异或运算
需求:
一个数组中有一种数出现K次,其他数都出现了M次,M>1,K<M.
要求:
如果这个数出现了K次,返回这个数,
如果这个数出现次数不等于K,返回-1
额外空间复杂度o(1),时间复杂度o(N)
分析
1. new1一个32位的数组t
2. 把目标数组arr,每一个元素,分解成一个32位的 二进制数,并用数组t,记录每一位的1出现的次数
- t[0] 0位置的1出现了几个
- t[1] 1位置的1出现了几个
- t[i] i位置的1出现了几个
- …
复制代码
1
2
3
4
5
6
7
8
9int[] t = new int[32]; // t[0] 0位置的1出现了几个 // t[i] i位置的1出现了几个 for (int num : arr) { for (int i = 0; i <=31 ; i++) { t[i]+=(num>>i)&1; } }
3. 数组t现在相当于是 一个 32位容器,每一个位都装了,目标数组,所有元素,相同位数下的1的数据和.
4.数组t的每一位,取模m,
- 如果t[i] % m == 0,表示我们要找的出现K次数,分解成32位二进制数时,在i位置上,是0
- t[i] % m != 0,表示我们要找的出现K次数,分解成32位二进制数时,在i位置上,是1
如果t[i] % m == k
- 如果取模结果等于k,表名这个出现K次数存在,我们就记录他的位置.
ans |= (1 << i);---------用int ans = 0;亦或 (1 << i) 来保存
如果取模结果t[i] % m != k
- 如果取模结果不等于k,表名这个数出现次数不等于K,返回-1
return -1;
复制代码
1
2
3
4
5
6
7
8
9
10
11int ans = 0; for (int i = 0; i < 32; i++) { if (t[i] % m != 0) { if (t[i] % m == k) { ans |= (1 << i); } else { return -1; } } }
5.临界值0的情况是
-
0是特殊情况,因为0,分解成32位2进制数时,任何位置上都是0,
-
0数组里出现多少次都不走上述-1那条逻辑链
-
所以 0 这个数的出现的次数 要最后再判断一下,是不是等于K次
复制代码
1
2
3
4
5
6
7
8
9
10
11
12if (ans == 0) { int count = 0; for (int num : arr) { if (num == 0) { count++; } } if (count != k) { return -1; } }
解法代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35// 请保证arr中，只有一种数出现了K次，其他数都出现了M次 public static int onlyKTimes(int[] arr, int k, int m) { int[] t = new int[32]; // t[0] 0位置的1出现了几个 // t[i] i位置的1出现了几个 for (int num : arr) { for (int i = 0; i <=31 ; i++) { t[i]+=(num>>i)&1; } } int ans = 0; for (int i = 0; i < 32; i++) { if (t[i] % m != 0) { if (t[i] % m == k) { ans |= (1 << i); } else { return -1; } } } if (ans == 0) { int count = 0; for (int num : arr) { if (num == 0) { count++; } } if (count != k) { return -1; } } return ans; }
对数器
1.用map来求此问题
- key来记录目标数组的元素的值
- value 来记录key元素出现的次数
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public static int test(int[] arr, int k, int m) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : arr) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } for (int num : map.keySet()) { if (map.get(num) == k) { return num; } } return -1; }
2 随机造数
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70public static void main(String[] args) { int kinds = 5; int range = 30; int testTime = 100000; int max = 9; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int a = (int) (Math.random() * max) + 1; // a 1 ~ 9 int b = (int) (Math.random() * max) + 1; // b 1 ~ 9 int k = Math.min(a, b); int m = Math.max(a, b); // k < m if (k == m) { m++; } int[] arr = randomArray(kinds, range, k, m); int ans1 = test(arr, k, m); int ans2 = onlyKTimes(arr, k, m); if (ans1 != ans2) { System.out.println(ans1); System.out.println(ans2); System.out.println("出错了！"); } } System.out.println("测试结束"); } public static int[] randomArray(int maxKinds, int range, int k, int m) { int ktimeNum = randomNumber(range); // 真命天子出现的次数 int times = Math.random() < 0.5 ? k : ((int) (Math.random() * (m - 1)) + 1); // 2 int numKinds = (int) (Math.random() * maxKinds) + 2; // k * 1 + (numKinds - 1) * m int[] arr = new int[times + (numKinds - 1) * m]; int index = 0; for (; index < times; index++) { arr[index] = ktimeNum; } numKinds--; HashSet<Integer> set = new HashSet<>(); set.add(ktimeNum); while (numKinds != 0) { int curNum = 0; do { curNum = randomNumber(range); } while (set.contains(curNum)); set.add(curNum); numKinds--; for (int i = 0; i < m; i++) { arr[index++] = curNum; } } // arr 填好了 for (int i = 0; i < arr.length; i++) { // i 位置的数，我想随机和j位置的数做交换 int j = (int) (Math.random() * arr.length);// 0 ~ N-1 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } return arr; } // [-range, +range] public static int randomNumber(int range) { return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1)); }
全部代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139package main.java.month1; import java.util.HashMap; import java.util.HashSet; public class class04 { public static int test(int[] arr, int k, int m) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : arr) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } for (int num : map.keySet()) { if (map.get(num) == k) { return num; } } return -1; } // 请保证arr中，只有一种数出现了K次，其他数都出现了M次 public static int onlyKTimes(int[] arr, int k, int m) { int[] t = new int[32]; // t[0] 0位置的1出现了几个 // t[i] i位置的1出现了几个 for (int num : arr) { for (int i = 0; i <=31 ; i++) { t[i]+=(num>>i)&1; } } int ans = 0; for (int i = 0; i < 32; i++) { if (t[i] % m != 0) { if (t[i] % m == k) { ans |= (1 << i); } else { return -1; } } } if (ans == 0) { int count = 0; for (int num : arr) { if (num == 0) { count++; } } if (count != k) { return -1; } } return ans; } public static int[] randomArray(int maxKinds, int range, int k, int m) { int ktimeNum = randomNumber(range); // 真命天子出现的次数 int times = Math.random() < 0.5 ? k : ((int) (Math.random() * (m - 1)) + 1); // 2 int numKinds = (int) (Math.random() * maxKinds) + 2; // k * 1 + (numKinds - 1) * m int[] arr = new int[times + (numKinds - 1) * m]; int index = 0; for (; index < times; index++) { arr[index] = ktimeNum; } numKinds--; HashSet<Integer> set = new HashSet<>(); set.add(ktimeNum); while (numKinds != 0) { int curNum = 0; do { curNum = randomNumber(range); } while (set.contains(curNum)); set.add(curNum); numKinds--; for (int i = 0; i < m; i++) { arr[index++] = curNum; } } // arr 填好了 for (int i = 0; i < arr.length; i++) { // i 位置的数，我想随机和j位置的数做交换 int j = (int) (Math.random() * arr.length);// 0 ~ N-1 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } return arr; } // [-range, +range] public static int randomNumber(int range) { return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1)); } public static void main(String[] args) { int kinds = 5; int range = 30; int testTime = 100000; int max = 9; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int a = (int) (Math.random() * max) + 1; // a 1 ~ 9 int b = (int) (Math.random() * max) + 1; // b 1 ~ 9 int k = Math.min(a, b); int m = Math.max(a, b); // k < m if (k == m) { m++; } int[] arr = randomArray(kinds, range, k, m); int ans1 = test(arr, k, m); int ans2 = onlyKTimes(arr, k, m); if (ans1 != ans2) { System.out.println(ans1); System.out.println(ans2); System.out.println("出错了！"); } } System.out.println("测试结束"); } }
最后
以上就是勤奋玉米最近收集整理的关于异或运算--01---arr中，只有一种数出现了K次，其他数都出现了M次异或运算题的全部内容，更多相关异或运算--01---arr中内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复