数组中有一个数字出现的次数超过数组的一半，请找出这个数字
解题方法（1）使用HashMap
解题思路：遍历整个数组，将数值作为键，出现的次数作为值保存到HashMap中，数组遍历结束后，再遍历HashMap，将值大于数组长度一半的键返回
编码实现
package com.company.algorithm;
import java.util.HashMap;
import java.util.Map;
public class FindEleMoreArraysLengthHalf {
public static void main(String[] args) {
FindEleMoreArraysLengthHalf findEleMoreArraysLengthHalf = new FindEleMoreArraysLengthHalf();
System.out.println(findEleMoreArraysLengthHalf.FindEleMoreArraysLengthHalf1(new int[]{1, 2, 3, 4, 1, 1, 3, 1, 1}));
}
private int FindEleMoreArraysLengthHalf1(int[] nums) {
HashMap map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (Map.Entry m : map.entrySet()) {
if (m.getValue() > nums.length / 2) return m.getKey();
}
return -1;
}
}
运行结果
D:JavaJDKbinjava.exe "-javaagent:D:IntelliJ IDEA 2019.3.3libidea_rt.jar=5089:D:IntelliJ IDEA 2019.3.3bin" -Dfile.encoding=UTF-8 -classpath D:JavaJDKjrelibcharsets.jar;D:JavaJDKjrelibdeploy.jar;D:JavaJDKjrelibextaccess-bridge-64.jar;D:JavaJDKjrelibextcldrdata.jar;D:JavaJDKjrelibextdnsns.jar;D:JavaJDKjrelibextjaccess.jar;D:JavaJDKjrelibextjfxrt.jar;D:JavaJDKjrelibextlocaledata.jar;D:JavaJDKjrelibextnashorn.jar;D:JavaJDKjrelibextsunec.jar;D:JavaJDKjrelibextsunjce_provider.jar;D:JavaJDKjrelibextsunmscapi.jar;D:JavaJDKjrelibextsunpkcs11.jar;D:JavaJDKjrelibextzipfs.jar;D:JavaJDKjrelibjavaws.jar;D:JavaJDKjrelibjce.jar;D:JavaJDKjrelibjfr.jar;D:JavaJDKjrelibjfxswt.jar;D:JavaJDKjrelibjsse.jar;D:JavaJDKjrelibmanagement-agent.jar;D:JavaJDKjrelibplugin.jar;D:JavaJDKjrelibresources.jar;D:JavaJDKjrelibrt.jar;D:JavaWorkSpaceday11outproductionalgorithm com.company.algorithm.FindEleMoreArraysLengthHalf 1
（2）排序取值
解题思路：对数组进行排序，排序后，处于中间位置的元素一定是出现次数超过一般的数
编码实现
package com.company.algorithm;
public class FindEleMoreArraysLengthHalf {
public static void main(String[] args) {
FindEleMoreArraysLengthHalf findEleMoreArraysLengthHalf = new FindEleMoreArraysLengthHalf();
System.out.println(findEleMoreArraysLengthHalf.FindEleMoreArraysLengthHalf2(new int[]{1, 2, 3, 4, 1, 1, 3, 1, 1}));
}
//使用的冒泡排序
private int FindEleMoreArraysLengthHalf2(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums[nums.length / 2];
}
}
运行结果
D:JavaJDKbinjava.exe "-javaagent:D:IntelliJ IDEA 2019.3.3libidea_rt.jar=5089:D:IntelliJ IDEA 2019.3.3bin" -Dfile.encoding=UTF-8 -classpath D:JavaJDKjrelibcharsets.jar;D:JavaJDKjrelibdeploy.jar;D:JavaJDKjrelibextaccess-bridge-64.jar;D:JavaJDKjrelibextcldrdata.jar;D:JavaJDKjrelibextdnsns.jar;D:JavaJDKjrelibextjaccess.jar;D:JavaJDKjrelibextjfxrt.jar;D:JavaJDKjrelibextlocaledata.jar;D:JavaJDKjrelibextnashorn.jar;D:JavaJDKjrelibextsunec.jar;D:JavaJDKjrelibextsunjce_provider.jar;D:JavaJDKjrelibextsunmscapi.jar;D:JavaJDKjrelibextsunpkcs11.jar;D:JavaJDKjrelibextzipfs.jar;D:JavaJDKjrelibjavaws.jar;D:JavaJDKjrelibjce.jar;D:JavaJDKjrelibjfr.jar;D:JavaJDKjrelibjfxswt.jar;D:JavaJDKjrelibjsse.jar;D:JavaJDKjrelibmanagement-agent.jar;D:JavaJDKjrelibplugin.jar;D:JavaJDKjrelibresources.jar;D:JavaJDKjrelibrt.jar;D:JavaWorkSpaceday11outproductionalgorithm com.company.algorithm.FindEleMoreArraysLengthHalf 1
（3）
解题思路：
编码实现
package com.company.algorithm;
public class FindEleMoreArraysLengthHalf {
public static void main(String[] args) {
FindEleMoreArraysLengthHalf findEleMoreArraysLengthHalf = new FindEleMoreArraysLengthHalf();
System.out.println(findEleMoreArraysLengthHalf.FindEleMoreArraysLengthHalf3(new int[]{1, 2, 3, 4, 1, 1, 3, 1, 1}));
}
private int FindEleMoreArraysLengthHalf3(int[] nums) {
int result = nums[0];
int times = 1;
for (int i = 1; i < nums.length; i++) {
if (times == 0) {
result = nums[i];
times = 1;
}
if (result == nums[i]) {
times++;
} else {
times--;
}
}
return result;
}
}
运行结果
