数据结构与算法 Python语言实现 第三章练习

巩固

# R-3.2
# n0 = 16

# R-3.3
# n0 = 20

# R-3.4
# 常数函数,线性函数?

# R-3.5
# logn的c次方 = clogn 斜率是固定常数,故为直线

# R-3.6
# 2*(0 + 1 + 2 + ... + n) = 2*(n*(n+1))/2 = n*(n+1)

# R-3.7
# 大O表示法表示的是最坏情况下的算法复杂度

# R-3.23
O(n)

# R-3.24
O(n)

# R-3.25
O(n²)

# R-3.26
O(n)

# R-3.27
O(n³)

# R-3.29
O(nlogn)

# R-3.30
O(nlogn)

# R-3.31
最好运行时间: O(nlogn)
最坏运行时间: O(n²)

# R-3.32
O(n)

# R-3.33
有干扰因素,当数值较小时,干扰因素影响较大

# R-3.34
1/1 + 1/2 + 1/3 + ... + 1/j + ... + 1/n (n调和数)

巩固部分代码参考

创新

# C-3.35
# 使用排序加遍历相邻三数是否相同: O(nlogn) + O(n) ---> O(nlogn)

# C-3.36
import random


class GetBigNum:
    def __init__(self, data):
        self.data = data
        self.n = len(data)

    def get_some_bigger(self, num):
        bigger_data = []
        while len(self.data) > self.n - num:
            max_val = self.get_max()
            bigger_data.append(max_val)
            self.data.remove(max_val)
        return bigger_data

    def get_max(self):
        max_val = self.data[0]
        for i in range(1, len(self.data)):
            if self.data[i] > max_val:
                max_val = self.data[i]
        return max_val


# 算法运行时间:O(n)
# test_data = [1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 14, 15, 15, 16, 17, 18, 19]
# big_num = GetBigNum(test_data)
# print(big_num.get_some_bigger(10))

# 或者使用排序加data[-10:]  O(nlogn)

# C-3.45
# def find_unique_lost(s):
#     total = 1
#     for i in range(len(s) + 1):
#         total *= (i + 1)
#     for j in s:
#         total /= (j + 1)
#     return int(total - 1)


# test_s = [0, 1, 2, 3, 4, 6]
# print(find_unique_lost(test_s))


# C-3.46
# 2只绵羊是特例


# C-3.50
# 1.
def sum_num(x, n, data):
    sum_result = 0

    for i in range(n+1):
        sum_xi = 1
        for j in range(i):
            sum_xi *= x
        sum_result += data[i] * sum_xi
    return sum_result


# print(sum_num(2, 3, [1, 2, 3, 4]))


# 2.
def sum_num2(x, n, data):
    sum_result = 0
    sum_xi = 1
    for i in range(n+1):
        sum_xi *= x
        sum_result += data[i] * sum_xi
    return sum_result / x


# print(sum_num2(2, 3, [1, 2, 3, 4]))


# C-3.54
from collections import defaultdict

def get_max_amount(data):
    total_amount = 0
    n = len(data)
    max_amount = 0
    max_amount_dic = defaultdict()
    max_amount_dic[‘max_amount‘] = dict()
    while total_amount < n:
        for i in range(n):
            val_amount = 1
            for val in data[i+1:]:
                if data[i] == val:
                    val_amount += 1
            if val_amount >= max_amount:
                max_amount = val_amount
                max_amount_val = set()
                max_amount_val.add(data[i])
                if max_amount in max_amount_dic[‘max_amount‘]:
                    max_amount_val.update(max_amount_dic[‘max_amount‘])
                max_amount_dic[‘max_amount‘] = {max_amount: max_amount_val}
                total_amount += val_amount
    return max_amount_dic


# test_data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 60]
# print(get_max_amount(test_data))
#
# S = []
# for i in range(1000):
#     S.append(random.randint(0, 4000))
# print(get_max_amount(S))


# 更优解
def find_most_frequent(n):
    s = []
    for _ in range(n):
        s.append(random.randint(0, 4*n - 1))

    restore_list = [0] * (4*n)
    most_int = 0
    for num in s:
        restore_list[num] += 1
        if restore_list[num] >= restore_list[most_int]:
            most_int = num
    if most_int == 1:
        return False
    else:
        return most_int, restore_list[most_int]


print(find_most_frequent(1000))

创新部分代码参考