题目描述
给出一个序列包含 n 个正整数的序列 A, 然后给出一个正整数 x, 你可以对序列进行任意次操作的, 每次操作你可以选择序列中的一个数字, 让其与 x 做按位或运算. 你的目的是让这个序列中的众数出现的次数最多.
请问众数最多出现多少次.
输入
输入第一行仅包含两个正整数 n 和 x, 表示给出的序列的长度和给定的正整数.
(1<=n<=100000,1<=x<=1000)
接下来一行有 n 个正整数, 即这个序列, 中间用空格隔开.(1<=a_i<=1000)
输出
输出仅包含一个正整数, 表示众数最多出现的次数.
样例输入
5 2
3 1 3 2 5
样例输出
3
思路分析:
从题目中提取出两点:
1, 可与 x 按位与运算操作, 也可不变
2, 统计处理后的数组中, 出现次数最多的数字的出现次数, 即众数出现的次数.
如 1:java 中直接可以用 "|" 或运算符对两个整数进行或运算.
如 2:
1用一个数组, 记录下原数组个数字出现的次数, 因题目中要求 1<=n<=100000, 所以这里可以创建一个长度为 100000 的数组, 来统计没个数字出现的次数.
2数组里的值是对应下标出现出现的次数, 例如 count[30]的值就是 30 这个数出现的次数.
3统计过程中, 并用变量 max 记录下最大的值.
4再将这个数与 x 进行或运算, 如果相同, 则不做任何操作, 如果不同, 则将或运算后的数字出现的次数 + 1, 并与 max 进行比较, 记录下当前最大值.
5循环结束, 得到的数组是经过变换后, 每个数最多能出现的次数, 那 max 就是出现次数最多的数字的出现次数, 即众数出现的次数.
举例:
原数组:[3 3 4 2 5 6 7]
x 为 4,
重复上诉思路中的步骤:
从上图中可以看出, 经过与 4 相或后统计, 7 出现的次数最多, 所以最终输出的就是 7 出现的次数, 即 3.
在这, 可能有人会问, 为什么要把原数组和相或之后的数组中某个数出现的次数统计在一块,
从图中可以看出, 统计到的每一个数, 都是由不同的数 (原数或者相或之后的数) 得到的, 所以统计原数组及去掉重复后的相或的结果, 是经过变换后每个数最多能出现的次数.
java 代码如下:
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int x = sc.nextInt();
- int[] arr = new int[n];
- int max = 0;
- int y = 0;
- int[] count = new int[1000000];
- for (int i = 0; i <n; i++) {
- arr[i] = sc.nextInt();
- count[arr[i]]++;
- if(count[arr[i]]>max)
- max = count[arr[i]];
- y= arr[i]|x;
- if(y!=arr[i]) {
- count[y]++;
- if(count[y]>max)
- max = count[y];
- }
- }
- System.out.println(max);
- }
- }
来源: http://www.bubuko.com/infodetail-3461682.html