首页 > python教程

Python 找出出现次数超过数组长度一半的元素实例

时间:2020-07-10 python教程 查看: 1015

利用问题的普遍性和特殊性来求解,

代码如下:

import unittest
from datetime import datetime

class GetFreqNumbersFromList(unittest.TestCase):
 def setUp(self):
  print("\n")
  self.start_time = datetime.now()
  print(f"{self._testMethodName} start: {self.start_time}")

 def tearDown(self):
  self.end_time = datetime.now()
  print(f"{self._testMethodName} end: {self.end_time}")
  exec_time = (self.end_time - self.start_time).microseconds
  print(f"{self._testMethodName} exec_time: {exec_time}")

 def normal_solution(self, _list, _debug=False):
  """
  普遍性解法
  利用字典记录每个元素出现的次数——然后找出元素出现次数超过数组长度一半的元素
  普遍性解法针对任何次数的统计均适用而不光只是针对出现次数超过数组长度一半的情况
  """
  _target = len(_list) // 2
  _dict = {}
  for _member in _list:
   if _member not in _dict:
    _dict.setdefault(_member, 1)
   else:
    _dict[_member] += 1
  _ret = [_member for _member in _dict if _dict[_member] > _target]
  if _debug:
   print(_ret)
  return _ret

 def specific_solution(self, _list, _debug=False):
  """
  特殊性解法
  假设有两个元素出现的次数都超过数组长度一半就会得出两个元素出现的次数超出了数组长度的矛盾结果——所以超过数组长度一半的元素是唯一的
  排序后在数组中间的一定是目标解
  特殊性解法只能针对元素出现次数超过数组长度一半的情况
  """
  _list.sort()
  if _debug:
   print(_list[len(_list) // 2])
  return _list[len(_list) // 2]

 def test_normal_solution(self):
  actual_result = self.normal_solution([2,2,2,2,2,2,1,1,1,1,1], False)
  self.assertEqual(actual_result[0], 2)

 def test_specific_solution(self):
  actual_result = self.specific_solution([2,2,2,2,2,2,1,1,1,1,1], False)
  self.assertEqual(actual_result, 2)

if __name__ == "__main__":
 # 找出出现次数超过数组长度一半的元素
 suite = unittest.TestSuite()
 suite.addTest(GetFreqNumbersFromList('test_normal_solution'))
 suite.addTest(GetFreqNumbersFromList('test_specific_solution'))
 runner = unittest.TextTestRunner()
 runner.run(suite)

测试结果:

补充知识:Python 用积分思想计算圆周率

早上起来突然想求圆周率,1单位时圆的面积。

代码如下:

from math import pow, sqrt

def calc_circle_s_with(r, dy, x_slices):
  x_from_start_to_cc = sqrt(1 - pow(dy, 2))
  dx = x_from_start_to_cc / x_slices
  x_to_edge = 1 - x_from_start_to_cc
  quarter_circle_s = 0
  while x_to_edge < 1:
    rect_s = dy * dx
    quarter_circle_s += rect_s
    x_to_edge = x_to_edge + dx
    dy = sqrt(1 - pow((1 - x_to_edge), 2))
  circle_s = 4 * quarter_circle_s
  print(circle_s)

calc_circle_s_with(1, 0.0001, 10000000)

运行结果接近3.1415926,dy传的越小,x_slices传的越大,就越接近。

半径为:1

初始小矩形到圆周的距离:1 - x_from_start_to_cc

其中dy代表四分之一圆中初始小矩形的高度,x_slices代表小矩形的宽度:(1 - x_from_start_to_cc) / x_slices

四分之一圆的面积积分为:quarter_circle_s

以上这篇Python 找出出现次数超过数组长度一半的元素实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持python博客。

展开全文
上一篇:Python实现发票自动校核微信机器人的方法
下一篇:python将dict中的unicode打印成中文实例
输入字:
相关知识
Python 实现图片色彩转换案例

我们在看动漫、影视作品中,当人物在回忆过程中,体现出来的画面一般都是黑白或者褐色的。本文将提供将图片色彩转为黑白或者褐色风格的案例详解,感兴趣的小伙伴可以了解一下。

python初学定义函数

这篇文章主要为大家介绍了python的定义函数,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能够给你带来帮助,希望能够给你带来帮助

图文详解Python如何导入自己编写的py文件

有时候自己写了一个py文件,想要把它导入到另一个py文件里面,所以下面这篇文章主要给大家介绍了关于Python如何导入自己编写的py文件的相关资料,需要的朋友可以参考下

python二分法查找实例代码

二分算法是一种效率比较高的查找算法,其输入的是一个有序的元素列表,如果查找元素包含在列表中,二分查找返回其位置,否则返回NONE,下面这篇文章主要给大家介绍了关于python二分法查找的相关资料,需要的朋友可以参考下