[PHP] 算法-数组中出现次数超过一半的数字的PHP实现

<div class="cnblogs_code">

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,5,4,2两种方式：

1.定义一个新数组arr，遍历数组给arr赋值，arr[元素]=<span style="color: #000000">出现的次数

2.排序下arr,取第一个的key和value,<span style="color: #000000">key是目标元素，value是出现次数，验证下后返回

3.<span style="color: #000000">时间复杂度是O(n) 空间上会新创建个数组

1.<span style="color: #000000">定义变量e代表出现次数最多的元素，变量count用于判断出现次数用

2.遍历数组，当前元素与e比较，相同的count++,不同的count--,<span style="color: #000000">count为0时当前元素覆盖e

3.<span style="color: #000000">遍历数组验证e所出现的次数有没有超过一半

4.<span style="color: #000000">时间复杂度O(n)  空间复杂度O(n)
e,<span style="color: #008080">count=1

<span style="color: #0000ff">for i=1;i<arr.length;i++

<span style="color: #0000ff">if arr[i]==<span style="color: #000000">e

<span style="color: #008080">count++

<span style="color: #0000ff">else

<span style="color: #008080">count--

<span style="color: #0000ff">if <span style="color: #008080">count==0<span style="color: #000000">

e=<span style="color: #000000">arr[i]

<span style="color: #008080">count=1

<span style="color: #008080">count=0

<span style="color: #0000ff">for i=0;i<arr.length;i++

<span style="color: #0000ff">if arr[i]==<span style="color: #000000">e

<span style="color: #008080">count++

<span style="color: #0000ff">if <span style="color: #008080">count*2>arr.<span style="color: #000000">length

<span style="color: #0000ff">return e

            </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$count</span>==0<span style="color: #000000"&gt;){
                    </span><span style="color: #800080"&gt;$e</span>=<span style="color: #800080"&gt;$arr</span>[<span style="color: #800080"&gt;$i</span><span style="color: #000000"&gt;];
                    </span><span style="color: #800080"&gt;$count</span>=1<span style="color: #000000"&gt;;
            }   
    }   
    </span><span style="color: #800080"&gt;$count</span>=0<span style="color: #000000"&gt;;
    </span><span style="color: #0000ff"&gt;for</span>(<span style="color: #800080"&gt;$i</span>=0;<span style="color: #800080"&gt;$i</span><<span style="color: #800080"&gt;$length</span>;<span style="color: #800080"&gt;$i</span>++<span style="color: #000000"&gt;){
            </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$arr</span>[<span style="color: #800080"&gt;$i</span>]==<span style="color: #800080"&gt;$e</span><span style="color: #000000"&gt;){
                    </span><span style="color: #800080"&gt;$count</span>++<span style="color: #000000"&gt;;
            }   
    }   
    </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$count</span>*2><span style="color: #800080"&gt;$length</span><span style="color: #000000"&gt;){
            </span><span style="color: #0000ff"&gt;return</span> <span style="color: #800080"&gt;$e</span><span style="color: #000000"&gt;; 
    }   
    </span><span style="color: #0000ff"&gt;return</span> 0<span style="color: #000000"&gt;;

}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!