Skip to content

Instantly share code, notes, and snippets.

@lttzzlll
Created May 17, 2018 06:36
Show Gist options
  • Save lttzzlll/fe623ac58a2f6c2d64b2903178728096 to your computer and use it in GitHub Desktop.
Save lttzzlll/fe623ac58a2f6c2d64b2903178728096 to your computer and use it in GitHub Desktop.
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()
@lttzzlll
Copy link
Author

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

@lttzzlll
Copy link
Author

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()

@lttzzlll
Copy link
Author

优化,提前终止。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment