题目描述

  • 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
  • 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
  • 由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
  • 如果不存在则输出0。

解法1

  • 使用map,键存元素,值存出现的次数
  • 发现有某个元素的次数超过数组长度的一半,则返回该元素

代码实现

  1. public int moreThanHalfNum(int [] array) {
  2. if(array == null || array.length == 0){
  3. return 0;
  4. }
  5. int flag = 0;
  6. Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  7. int len = array.length;
  8. for(int i = 0; i < len; i++){
  9. if(map.containsKey(array[i])){
  10. map.put(array[i], map.get(array[i]) + 1);
  11. }else{
  12. map.put(array[i], 1);
  13. }
  14. if(map.get(array[i]) > len / 2){
  15. flag = array[i];
  16. break;
  17. }
  18. }
  19. return flag;
  20. }

解法2

  • 设置标识变量,遇到相同的数字,就把次数加1,如果没有遇到就把次数减1
  • 由于要找的数字出现的次数一定大于其他数字出现次数之和
  • 所以那个数字肯定是最后一次吧times变量设为1对应的数字

代码实现

  1. public int moreThanHalfNum(int[] array) {
  2. if(array == null || array.length == 0){
  3. return 0;
  4. }
  5. int times = 1;
  6. int result = array[0];
  7. for(int i = 1; i < array.length; i++){
  8. if(times == 0){
  9. result = array[i];
  10. times = 1;
  11. }else if(array[i] == result){
  12. //遇到相同的数字次数就加1
  13. times++;
  14. }else{
  15. //没有遇到相同的就把次数减1
  16. times--;
  17. }
  18. }
  19. if(!checkMoreThanHalfNum(array, result)){
  20. return 0;
  21. }
  22. return result;
  23. }
  24. //检查该数字是否出现的次数超过一半
  25. private boolean checkMoreThanHalfNum(int[] array, int result){
  26. int times = 0;
  27. for(int i = 0; i < array.length; i++){
  28. if(array[i] == result){
  29. times++;
  30. }
  31. }
  32. boolean isMoreThanHalf = true;
  33. if(times * 2 <= array.length){
  34. isMoreThanHalf = false;
  35. }
  36. return isMoreThanHalf;
  37. }