超过一半的数字
2023-03-14 09:45:35 时间
题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
思路:解法一、排序完后返回arr[N/2] O(nlgn) Arrays.sort(arr); System.out.println(arr[N/2]);
解法二、hash统计
解法三、顺序统计,就跟寻找乱序数组中第K大的数解法一样。O(N),那么这里就是求乱序数组中第N/2大的数,限制:需要改动数组的内容
解法四、不同的数,进行消除
代码:
public class MoreThanHalf { public static void main(String[] args) { f(new int[]{5,6,6,6,2,3,6}); } // 不同的数,进行消除,O(N) public static void f(int arr[]){ //候选数 先定位第一个元素 int candidate = arr[0]; // 出现的次数 int nTimes = 1; // 扫描数组 for (int i = 1; i < arr.length; i++) { // 两两消减为0,应该把现在的元素作为候选值 if (nTimes==0 ) { candidate = arr[i]; nTimes = 1; continue; } // 如果遇到和候选值相同的,次数加一 if (arr[i]==candidate) { nTimes++; // 不同的数,进行消减 }else { nTimes--; } } //System.out.println(nTimes); if (nTimes==0) { System.out.println(-1); }else { System.out.println(candidate); } } }
结果:
趣味拓展:加强版水王问题,假如出现的次数恰好为个数的一般,求出这个数。
思路:有个巧妙的方法扫描一遍数组就解决问题,水王发的贴子占总数的一半,说明总数为偶数;不失一般性,假设隔一个数就是水王的id,两两不同最后一定会消减为0,如果水王是最后一个元素,那么每次扫描的时候,多一个动作,和最后一个元素做比较,单独计数,计数恰好一半。如果不是,那么去掉最后一个元素,水王就是留下的那么candidate。
代码:
public class MoreThanHalf { public static void main(String[] args) { //进行测试数据要满足测试条件 不然结果会错误 f(new int[]{6,6,6,5,6,1,2,3,4,6}); } // 不同的数,进行消除,O(N) public static void f(int arr[]){ //候选数 先定位第一个元素 int candidate = arr[0]; // 出现的次数 int nTimes = 1; int countOfLast = 1; // 统计这个元素出现的次数 // 扫描数组 for (int i = 1; i < arr.length; i++) { if (arr[i-1]==arr[arr.length-1]) { countOfLast++; } // 两两消减为0,应该把现在的元素作为候选值 if (nTimes==0 ) { candidate = arr[i]; nTimes = 1; continue; } // 如果遇到和候选值相同的,次数加一 if (arr[i]==candidate) { nTimes++; // 不同的数,进行消减 }else { nTimes--; } } //System.out.println(nTimes); if (countOfLast==arr.length/2) { System.out.println(arr[arr.length-1]); }else { System.out.println(candidate); } } }
结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的