Python数据结构编程题

Python数据结构编程题 1.数组中出现次数超过一半的数字         思路：在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1 ，否则次数减 1 ；若次数为 0 ，则保存下一个数字，并将次数置为 1 。遍历结束 后，所保存的数字即为所求。然后再判断它是否符合条件即可。         时间复杂度:O(N)

def MoreThanHalfNum_Solution(numbers): 
    len1 = len(numbers)
    if len1==0:
        return 0 
    elif len1>=1:
        # 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        res = numbers[0] # 初始值
        count = 1 # 次数
        for i in range(1,len1): 
            if count == 0:
                # 更新result的值为当前元素，并置次数为1
                res = numbers[i] 
                count = 1
            elif numbers[i] == res: 
                count += 1 # 相同则加1
            elif numbers[i] != res: 
                count -= 1 # # 不同则加1
        # 判断res是否符合条件，即出现次数大于数组长度的一半
        counts = 0
        for j in range(len1):
            if numbers[j] == res: 
                counts += 1
            if counts>len1//2: 
                return res
            else:
                return 0

2.求100以内的质数

#求100以内的全部素数
L=[]
for x in range(100): 
    if x<2:
        continue
    for i in range(2,x): 
        if x%i==0:
            break
    else: #走到此处，x一定是素数
        L.append(x)
print("100以内的全部素数有：",L)