算法题练习——python题解BM52 数组中只出现一次的两个数字和BM51 数组中出现次数超过一半的数字

秒速五厘米 2024-04-06 09:27 50阅读 0赞

### BM52 数组中只出现一次的两个数字 ###

**描述**

> 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

**数据范围：**

> 数组长度 2≤n≤1000，数组中每个数的大小 0<val≤1000000

**要求：**

> 空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

**提示：**

> 输出时按非降序排列。

**示例1**

> 输入：\[1,4,1,6\]
> 
> 返回值：\[4,6\]
> 
> 说明：返回的结果中较小的数排在前面

**示例2**

> 输入：\[1,2,3,3,2,9\]
> 
> 返回值：\[1,9\]

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param array int整型一维数组 
    # @return int整型一维数组
    #
    class Solution:
        def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
            # write code here
            if len(array)==2:
                return array
            array.sort()
            out = []
            if array[-1] != array[-2]:
                out.append(array[-1])
                t = 1
            elif array[1] != array[0]:
                out.append(array[0])
                t = 1
            else:
                t = 0
            for i in range(1, len(array)-1):
                if array[i]!=array[i-1] and array[i]!= array[i+1]:
                    out.append(array[i])
                    t += 1
                if t == 2:
                    out.sort()
                    return out

--------------------

### BM51 数组中出现次数超过一半的数字 ###

**描述**

> 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

**例如：**

> 输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

**数据范围：**

> n≤50000，数组中元素的值 0≤val≤10000

**要求：**

> 空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)

**输入描述：**

> 保证数组输入非空，且保证有解

**示例1**

> 输入：\[1,2,3,2,2,2,5,4,2\]
> 
> 返回值：2

**示例2**

> 输入：\[3,3,3,3,2,2,2\]
> 
> 返回值：3

**示例3**

> 输入：\[1\]
> 
> 返回值：1

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param numbers int整型一维数组 
    # @return int整型
    #
    class Solution:
        def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
            # write code here
            nums = {}
            l = len(numbers)
            for index,num in enumerate(numbers):
                if num not in nums:
                    nums[num] = 1
                else:
                    nums[num] += 1
                if nums[num]>l/2:
                    return num
            return