数据结构算法(数组中出现次数超过一半的数字)
程序员文章站
2022-04-26 14:44:30
1. 本题知识点数组2. 题目描述数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次,超过数组长度的一半,因此输出 2。如果不存在则输出 0。3. 解题思路排序对数组进行排序取排序后数组的中间的元素,由于有一个数字出现的次数超过数组长度的一半,所以中间的元素一定就是这个数遍历数组,记录这个数出现的次数若出现次数超过数组长度一半,返回这个数否则返回 0使用...
1. 本题知识点
数组
2. 题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次,超过数组长度的一半,因此输出 2。如果不存在则输出 0。
3. 解题思路
排序
- 对数组进行排序
- 取排序后数组的中间的元素,由于有一个数字出现的次数超过数组长度的一半,所以中间的元素一定就是这个数
- 遍历数组,记录这个数出现的次数
- 若出现次数超过数组长度一半,返回这个数
- 否则返回 0
使用 HashMap
- 使用 HashMap 建立每个数和其出现次数的映射
- 在建立的过程中,若某个数出现次数超过数组长度的一半,返回这个数
- 否则返回 0
4. 代码
排序
import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int[] array) { // 对数组进行排序 Arrays.sort(array); // 取排序后数组的中间的元素 int num = array[array.length / 2]; // 该元素在数组中出现的次数 int count = 0; // 遍历数组 for (int i = 0; i < array.length; i++) { if (array[i] == num) { count++; } } // 若出现次数超过数组长度一半,返回这个数 if (count > array.length / 2) { return num; } // 否则返回 0 return 0; } }
使用 HashMap
import java.util.HashMap; public class Solution { public int MoreThanHalfNum_Solution(int[] array) { HashMap<Integer, Integer> hashMap = new HashMap<>(); // 使用 HashMap 建立每个数和其出现次数的映射 for (int i = 0; i < array.length; i++) { int num = array[i]; hashMap.put(num, hashMap.getOrDefault(num, 0) + 1); // 若某个数出现次数超过数组长度的一半,返回这个数 if (hashMap.get(num) > array.length / 2) { return num; } } // 否则返回 0 return 0; } }
本文地址:https://blog.csdn.net/bm1998/article/details/108032841
推荐阅读
-
PHP实现找出数组中出现次数超过数组长度一半的数字算法示例
-
[PHP] 算法-数组中出现次数超过一半的数字的PHP实现
-
LeetCode 面试题56 - I. 数组中数字出现的次数
-
数据结构算法(数组中出现次数超过一半的数字)
-
php实现数组中出现次数超过一半的数字的统计方法
-
在一个非降序排列的数组中,找出数字target出现的次数问题解答
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
【算法分享】剑指offer56-数组中只出现一次的两个数字
-
【算法-数组】找出数组中只出现一次的数字
-
剑指offer28.数组中出现次数超过一半的数字(Java)