half_most_num.py

import random
import unittest


def most_num(nums):
    cur = nums[0]
    cnt = 1
    for i in range(1, len(nums)):
        if cnt == 0:
            cur = nums[i]
            cnt = 1
        else:
            if nums[i] == cur:
                cnt += 1
            else:
                cnt -= 1
        # print(cur, nums[i], cnt)

    return cur

class TestMostNumber(unittest.TestCase):
    def setUp(self):
        self.nums = random.sample(range(0, 100), 10)
        self.most_num = random.randint(100, 1000)
        self.nums += [self.most_num] * 11
        random.shuffle(self.nums)

    def test_most_num(self):
        # print(self.nums)
        res = most_num(self.nums)
        self.assertEqual(res, self.most_num)

    def tearDown(self):
        self.nums = None


if __name__ == '__main__':
    unittest.main()

找到一个数组中数量多于一半的元素。

import random
import unittest


def most_num(nums):
    length = len(nums)
    cnt = 0
    for i in range(0, length):
        if cnt * 2 >= length:
            break
        if cnt == 0:
            cur = nums[i]
            cnt = 1
        else:
            if nums[i] == cur:
                cnt += 1
            else:
                cnt -= 1

    return cur


class TestMostNumber(unittest.TestCase):
    def setUp(self):
        self.nums = random.sample(range(0, 100), 10)
        self.most_num = random.randint(100, 1000)
        self.nums += [self.most_num] * 11
        random.shuffle(self.nums)

    def test_most_num(self):
        # print(self.nums)
        res = most_num(self.nums)
        self.assertEqual(res, self.most_num)

    def tearDown(self):
        self.nums = None


if __name__ == '__main__':
    unittest.main()

优化，提前终止。