编程练习：寻找发帖"水王"
2024-08-29 11:46:21
题目: 寻找发帖"水王"
- 来源: 编程之美
分析
- 衍生：就是给定一个数组，其中某个元素出现次数超过了数组长度的一半，找出这个元素
方法s
方法1
对这个串进行遍历，同时对出现的元素进行计数，可以用map，最后遍历map取出计数值最大的那个元素
方法2
可以对数组进行排序，第N/2个元素就是所求，下表从0开始
方法3
上面两个方法都有排序操作，时间复杂度不可观。
可以一次遍历, 在遍历过程中删除两个不同的元素(不管是不是出现次数最多的那个元素)，最后剩下的就是所求。
实现
/**
* @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;
}
}
泛型实现
这里默认是字符串数组，但是在实际运用时，肯定还有其他类型，所有采用泛型实现，问题就能迎刃而解；
/**
* @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;
}
- 调用
Integer arr[] = {1,2,3,1,2,1};
Demo1 demo1 = new Demo1();
System.out.println(demo1.func2(arr));
衍生问题
- 数组中存在3个元素，切出现次数超过了数组长度的1/4，求这三个元素
- 数组中存在1一个元素，出现次数刚好只有数组长度的一半，找出来
最后
生命不息，使劲造
最新文章
- Binary Agents
- WebView 上传文件 WebChromeClient之openFileChooser函数
- 非常实用的Ubuntu常用终端命令
- SQL Server使用规范（转）
- RIA Test：try catch 对 Error #1009 （无法访问空对象引用的属性或方法）的处理
- STM8S TIM1 PWM初始化设置
- java基础（二章）
- [POJ2406]字符串的幂
- Django之路由分发和反向解析
- 论JavaScript的作用域
- vue构造函数（根实例化时和组件实例对象选项）参数：选项详解
- （转）基于http协议的api接口对于客户端的身份认证方式以及安全措施
- Web大前端面试题-Day9
- python3之枚举
- delphi中的 IntToHex()
- 用yarn代替cnpm,cnpm漏包有点严重
- Oracle中序列（Sequence）详解
- Linux学习杂记
- [Jobdu] 题目1529：棋盘寻宝
- 2019年，200道面试题打造最受企业欢迎的iOS程序猿！