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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法 Python语言实现 第三章练习，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4111字，纯文字阅读大概需要6分钟。

内容图文

巩固

 1 # R-3.2
 2 # n0 = 16
 3 
 4 # R-3.3
 5 # n0 = 20
 6 
 7 # R-3.4
 8 # 常数函数,线性函数?
 9 
10 # R-3.5
11 # logn的c次方 = clogn 斜率是固定常数,故为直线
12 
13 # R-3.6
14 # 2*(0 + 1 + 2 + ... + n) = 2*(n*(n+1))/2 = n*(n+1)
15 
16 # R-3.7
17 # 大O表示法表示的是最坏情况下的算法复杂度
18 
19 # R-3.23
20 O(n)
21 
22 # R-3.24
23 O(n)
24 
25 # R-3.25
26 O(n²)
27 
28 # R-3.26
29 O(n)
30 
31 # R-3.27
32 O(n³)
33 
34 # R-3.29
35 O(nlogn)
36 
37 # R-3.30
38 O(nlogn)
39 
40 # R-3.31
41 最好运行时间: O(nlogn)
42 最坏运行时间: O(n²)
43 
44 # R-3.32
45 O(n)
46 
47 # R-3.33
48 有干扰因素,当数值较小时,干扰因素影响较大
49 
50 # R-3.34
51 1/1 + 1/2 + 1/3 + ... + 1/j + ... + 1/n (n调和数)

巩固部分代码参考

创新

  1 # C-3.35
  2 # 使用排序加遍历相邻三数是否相同: O(nlogn) + O(n) ---> O(nlogn)
  3 
  4 # C-3.36
  5 import random
  6 
  7 
  8 class GetBigNum:
  9     def __init__(self, data):
 10         self.data = data
 11         self.n = len(data)
 12 
 13     def get_some_bigger(self, num):
 14         bigger_data = []
 15         while len(self.data) > self.n - num:
 16             max_val = self.get_max()
 17             bigger_data.append(max_val)
 18             self.data.remove(max_val)
 19         return bigger_data
 20 
 21     def get_max(self):
 22         max_val = self.data[0]
 23         for i in range(1, len(self.data)):
 24             if self.data[i] > max_val:
 25                 max_val = self.data[i]
 26         return max_val
 27 
 28 
 29 # 算法运行时间:O(n)
 30 # test_data = [1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 14, 15, 15, 16, 17, 18, 19]
 31 # big_num = GetBigNum(test_data)
 32 # print(big_num.get_some_bigger(10))
 33 
 34 # 或者使用排序加data[-10:]  O(nlogn)
 35 
 36 # C-3.45
 37 # def find_unique_lost(s):
 38 #     total = 1
 39 #     for i in range(len(s) + 1):
 40 #         total *= (i + 1)
 41 #     for j in s:
 42 #         total /= (j + 1)
 43 #     return int(total - 1)
 44 
 45 
 46 # test_s = [0, 1, 2, 3, 4, 6]
 47 # print(find_unique_lost(test_s))
 48 
 49 
 50 # C-3.46
 51 # 2只绵羊是特例
 52 
 53 
 54 # C-3.50
 55 # 1.
 56 def sum_num(x, n, data):
 57     sum_result = 0
 58 
 59     for i in range(n+1):
 60         sum_xi = 1
 61         for j in range(i):
 62             sum_xi *= x
 63         sum_result += data[i] * sum_xi
 64     return sum_result
 65 
 66 
 67 # print(sum_num(2, 3, [1, 2, 3, 4]))
 68 
 69 
 70 # 2.
 71 def sum_num2(x, n, data):
 72     sum_result = 0
 73     sum_xi = 1
 74     for i in range(n+1):
 75         sum_xi *= x
 76         sum_result += data[i] * sum_xi
 77     return sum_result / x
 78 
 79 
 80 # print(sum_num2(2, 3, [1, 2, 3, 4]))
 81 
 82 
 83 # C-3.54
 84 from collections import defaultdict
 85 
 86 def get_max_amount(data):
 87     total_amount = 0
 88     n = len(data)
 89     max_amount = 0
 90     max_amount_dic = defaultdict()
 91     max_amount_dic['max_amount'] = dict()
 92     while total_amount < n:
 93         for i in range(n):
 94             val_amount = 1
 95             for val in data[i+1:]:
 96                 if data[i] == val:
 97                     val_amount += 1
 98             if val_amount >= max_amount:
 99                 max_amount = val_amount
100                 max_amount_val = set()
101                 max_amount_val.add(data[i])
102                 if max_amount in max_amount_dic['max_amount']:
103                     max_amount_val.update(max_amount_dic['max_amount'])
104                 max_amount_dic['max_amount'] = {max_amount: max_amount_val}
105                 total_amount += val_amount
106     return max_amount_dic
107 
108 
109 # test_data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 60]
110 # print(get_max_amount(test_data))
111 #
112 # S = []
113 # for i in range(1000):
114 #     S.append(random.randint(0, 4000))
115 # print(get_max_amount(S))
116 
117 
118 # 更优解
119 def find_most_frequent(n):
120     s = []
121     for _ in range(n):
122         s.append(random.randint(0, 4*n - 1))
123 
124     restore_list = [0] * (4*n)
125     most_int = 0
126     for num in s:
127         restore_list[num] += 1
128         if restore_list[num] >= restore_list[most_int]:
129             most_int = num
130     if most_int == 1:
131         return False
132     else:
133         return most_int, restore_list[most_int]
134 
135 
136 print(find_most_frequent(1000))

创新部分代码参考

 

内容总结

以上是互联网集市为您收集整理的数据结构与算法 Python语言实现 第三章练习全部内容，希望文章能够帮你解决数据结构与算法 Python语言实现 第三章练习所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---