php实现求数组中出现次数超过一半的数字（isset($arr[$val])）（取不同数看剩）（排序取中）

一、总结

1、if(isset($arr[$val])) $arr[$val]++; //1、isset函数

2、else $arr[$val]=1; //2、$arr[$val]而非$arr['$val']

二、php实现求数组中出现次数超过一半的数字

题目描述

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

三、代码

代码一：php 接近O（2n）

 1 <?php
 2 //算法：拿一个数组存数字，一个数组存数字出现的次数
 3 function MoreThanHalfNum_Solution($numbers)
 4 {
 5     $arr=array();
 6     foreach($numbers as $k=>$val){
 7         if(isset($arr[$val])) $arr[$val]++; //1、isset函数
 8         else $arr[$val]=1;  //2、$arr[$val]而非$arr['$val']
 9     }
10     $n=count($numbers)/2;
11     foreach($arr as $k=>$v){
12         if($v>$n) return $k;
13     }
14     return 0;
15 }

代码二：用户“分形叶”思路 O（n）

方法一：采用用户“分形叶”思路（注意到目标数 超过数组长度的一半，对数组同时去掉两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果），在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int length=array.length;
     if(array==null||length<=0){
     return 0;
     }

     if(length==1){
     return array[1];
     }

     int[] tempArray=new int[length];
     for(int i=0;i<length;i++){
     tempArray[i]=array[i];
     }

     for(int i=0;i<length;i++){
     //后面需要用零来代表抹除数字，所以对0时做特殊处理
     if(tempArray[i]==0){
     continue;
     }

     for(int j=i+1;j<length;j++){
          if(tempArray[i]!=tempArray[j]&&tempArray[j]!=0){
     tempArray[i]=0;//此处用0代表抹去该数字
     tempArray[j]=0;
     break;
     }

     }
     }

     for(int i=0;i<length;i++){
          System.out.println(tempArray[i]);
     }

     //找出未被抹去的数字
     int result=0;
     for(int i=0;i<length;i++){
     if(tempArray[i]!=0){
     result=tempArray[i];
     break;
     }
     }

     int times=0;
     for(int i=0;i<length;i++){
     if(result==array[i]){

     times++;
     }
     }

     if(times*2<length){
     result=0;
     }
     return result;
}
}

代码三：快排取中 O(NlogN)

数组排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等）

这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优；

 1 class Solution {
 2 public:
 3     int MoreThanHalfNum_Solution(vector<int> numbers)
 4     {
 5         // 因为用到了sort，时间复杂度O(NlogN)，并非最优
 6         if(numbers.empty()) return 0;
 7          
 8         sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数
 9         int middle = numbers[numbers.size()/2];
10          
11         int count=0; // 出现次数
12         for(int i=0;i<numbers.size();++i)
13         {
14             if(numbers[i]==middle) ++count;
15         }
16          
17         return (count>numbers.size()/2) ? middle :  0;
18     }
19 };

代码四：O（n）

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

前提条件是一定有个数超过一半的数存在，不然解不出来！

 1 class Solution {
 2 public:
 3     int MoreThanHalfNum_Solution(vector<int> numbers)
 4     {
 5         if(numbers.empty()) return 0;
 6          
 7         // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
 8         int result = numbers[0];
 9         int times = 1; // 次数
10          
11         for(int i=1;i<numbers.size();++i)
12         {
13             if(times == 0)
14             {
15                 // 更新result的值为当前元素，并置次数为1
16                 result = numbers[i];
17                 times = 1;
18             }
19             else if(numbers[i] == result)
20             {
21                 ++times; // 相同则加1
22             }
23             else
24             {
25                 --times; // 不同则减1               
26             }
27         }
28          
29         // 判断result是否符合条件，即出现次数大于数组长度的一半
30         times = 0;
31         for(int i=0;i<numbers.size();++i)
32         {
33             if(numbers[i] == result) ++times;
34         }
35          
36         return (times > numbers.size()/2) ? result : 0;
37     }
38 };