题目: 寻找发帖”水王”
- 来源: 编程之美
分析
- 衍生：就是给定一个数组，其中某个元素出现次数超过了数组长度的一半，找出这个元素
方法s
方法1
对这个串进行遍历，同时对出现的元素进行计数，可以用map，最后遍历map取出计数值最大的那个元素方法2
可以对数组进行排序，第N/2个元素就是所求，下表从0开始方法3
上面两个方法都有排序操作，时间复杂度不可观。可以一次遍历, 在遍历过程中删除两个不同的元素(不管是不是出现次数最多的那个元素)，最后剩下的就是所求。
实现
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/**
* @ClassName: Demo1
* @Author: fanjiajia
* @Date: 2018/12/19 下午8:35
* @Version: 1.0
* @Description: 某个字符串数组中存在出现次数超过该数组长度一半的某一个串，找出来
*/
public class Demo1 {
public static void main(String[] args) {
String strs[] = {"a","3", "a", "d","a", "4","6","a", "a"};
System.out.println(func1(strs));
}
/**
* @Author fanjiajia
* @Date 下午9:03 2018/12/19
* @Description
**/
public static String func1(String[] strs) {
/*
方法一: 遍历一次，对每一个串出现的次数进行累计
方法二: 按照出现的次数进行排序，第N/2个必然是这个串，下标从0开始
方法三: 上面的方法都会出现排序，时间复杂度高，可以一次遍历，直接获取
每一次删除其中两个不同的串，那么最后剩下的必然是我们所需要的
*/
String candidate = ""; // 保存可能是那个串
int nTimes, i; // nTimes操作逻辑：与之不匹配消除一对id时减少1，否则加1
for (i = nTimes = 0; i < strs.length; i++) {
if (nTimes == 0) { // ==0 说明遍历过程前面的都已经配对消除了
candidate = strs[i];
nTimes = 1;
}else { // 说明前面有某个串没有完全配对消除
if (strs[i] == candidate) // 当前串和那个串相同，则计数值+1，否则用当前这个不同的串进行消除
nTimes ++;
else
nTimes --;
}
}
return candidate;
}
}
泛型实现
这里默认是字符串数组，但是在实际运用时，肯定还有其他类型，所有采用泛型实现，问题就能迎刃而解；
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
* @Author fanjiajia
* @Date 下午7:50 2018/12/20
* @Description 数组中存在出现次数超过一半的元素，找出来，泛型实现
**/
public <T> T func2(T[] arr) {
T candidate = null;
int nTimes,i;
for (i = nTimes = 0; i < arr.length; i++) {
if (nTimes == 0) {
candidate = arr[i];
nTimes = 1;
}else {
if (arr[i] == candidate)
nTimes++;
else
nTimes--;
}
}
return candidate;
}
- 调用
1
2
3Integer arr[] = {1,2,3,1,2,1};
Demo1 demo1 = new Demo1();
System.out.println(demo1.func2(arr));
