找出数组中出现频率超过一半的数

我就是我 2022-09-18 10:56 174阅读 0赞

[开源中国][Link 1]

# [代码分享][Link 2] #

当前位置：

[代码分享][Link 2] »  [Python][]  »  [编程基础][Link 3]

[![Anomin][]][Anomin 1]

# [找出数组中出现频率超过一半的数][Link 4] #

[Anomin][Anomin 1] 发布于 2013年11月08日 13时, [ 2评/131阅][2_131]

**分享到 **

新浪微博 腾讯微博

收藏 \+1

踩 顶 0

有一个乱序的数组，其中有一个数占了一半以上，找出这个数  
三种方法： 1.一次遍历，筛掉两个不同的数，其剩余数组中，频率超过一半的数还是超过一半...  
                  2.排序， 选取中间的那个数，即是  
                  3.放到MAP中，选取频率最高的那个数

**标签：** <无>

## 代码片段*(1)**[\[全屏查看所有代码\]][Link 5]* ##

### *1. \[代码\]*找出数组中频率超过一般的数     ###

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>import</code> <code>random</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>specified </code><code>=</code> <code>4</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>05</code></td> 
   <td><code># generate standard sample</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>x</code><code>%</code><code>2</code> <code>=</code><code>=</code> <code> 0</code> <code>or</code> <code>x</code><code>%</code><code>7</code> <code>=</code><code>=</code> <code> 0</code><code>:</code><code>return</code> <code> specified</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>random.randint(</code><code>1</code><code>,</code><code>100</code><code>)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>09</code></td> 
   <td><code>array </code><code>=</code> <code>map</code><code>(f, </code><code>xrange</code><code>(</code><code>0</code><code>,</code><code>100</code><code>))</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>10</code></td> 
   <td><code>#random.shuffle(array)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>#print array.count(specified)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code># findout the value , Tree method to solve the question:</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>14</code></td> 
   <td><code>def</code> <code>findoutSpecifiedByIterOnce(array):</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp </code> <code>=</code> <code>array[</code><code>0</code><code>]</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>16</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>count </code> <code>=</code> <code>1</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>17</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code> <code>i </code><code>in</code> <code> xrange</code><code>(</code><code>1</code><code>, </code><code>len</code><code>(array)):</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>count </code><code>=</code><code>=</code> <code>0</code><code>:</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp </code><code>=</code> <code>array[i]</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>20</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>count </code><code>+</code><code>=</code> <code> 1</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>continue</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>temp </code><code>=</code><code>=</code> <code>array[i]:</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>23</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>count </code><code>+</code><code>=</code> <code> 1</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>25</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>count </code><code>-</code><code>=</code> <code> 1</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>#print "show ", temp</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>temp</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>29</code></td> 
   <td><code>def</code> <code>findoutSpecifiedBySort(array):</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>30</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>array.sort()</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>31</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>array[</code><code>len</code><code>(array)</code><code>/</code><code>2</code><code>]</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>33</code></td> 
   <td><code>def</code> <code>findoutSpecifiedByMap(array):</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>arrayCountMap </code><code>=</code> <code>{x : array.count(x) </code> <code>for</code> <code>x </code><code>in</code> <code>set</code><code>(array)}</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>35</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>sorted</code><code>(arrayCountMap.items(), key</code><code>=</code><code>lambda</code> <code>arrayCountMap:arrayCountMap[</code><code>1</code><code>], reverse</code><code>=</code><code>True</code><code>)[</code><code>0</code><code>][</code><code>0</code><code>]</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>38</code></td> 
   <td><code>print</code> <code>findoutSpecifiedByIterOnce(array) </code><code>=</code><code>=</code> <code> specified</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>39</code></td> 
   <td><code>print</code> <code>findoutSpecifiedByMap(array) </code><code>=</code><code>=</code> <code> specified</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>40</code></td> 
   <td><code>print</code> <code>findoutSpecifiedBySort(array) </code><code>=</code><code>=</code> <code> specified</code></td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: http://www.oschina.net/
[Link 2]: http://www.oschina.net/code/list
[Python]: http://www.oschina.net/code/list/?lang=python
[Link 3]: http://www.oschina.net/code/list/?catalog=programming-base
[Anomin]: /images/20220828/15a914eb87034db7bbb633816795c205.png
[Anomin 1]: http://my.oschina.net/u/921748
[Link 4]: http://www.oschina.net/code/snippet_921748_26254
[2_131]: http://www.oschina.net/code/snippet_921748_26254#comments
[Link 5]: http://www.oschina.net/code/piece_full?code=26254