https://colab.research.google.com/drive/1wPDdxFOkLYLVR_gg7TunmJdMd-QYjO-9?usp=sharing
存在N个石头，label 为0 - N-1，重量已知，找到一对石头，重量插值为 D
- N 石头数量
- D 重量差
- stone_weight_Range 石头重量范围，注：石头重量可能重复
from preamble import *
%matplotlib inline
import random
import copy
def find_same_weight(stone_weight):
""" 找到重量一样的石头,构造key值为重量，value值为[label] 的字典"""
s = time.time()
stone_weight2 = {}
for index, weight in enumerate(stone_weight):
if weight in stone_weight2:
stone_weight2[weight].append(index)
else:
stone_weight2[weight] = [index]
print("[find_same_weight]循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
return stone_weight2
def find_weight_difference(stone_weight2,D):
""" Weight difference"""
s = time.time()
hashmap = {}
for index, weight in enumerate(stone_weight2.keys()):
another_weight1 = weight + D
another_weight2 = weight - D
if another_weight1 in hashmap:
print("找到两块石头重量分别为 {} {} ".format(another_weight1,weight))
print("找到石头label分别为 {} {} ".format(stone_weight2[another_weight1],stone_weight2[weight]))
print("循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
if another_weight2 in hashmap:
print("找到两块石头重量分别为 {} {} ".format(another_weight2,weight))
print("找到石头label分别为 {} {} ".format(stone_weight2[another_weight2],stone_weight2[weight]))
print("循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
hashmap[weight] = index
print("[find_weight_difference]最多循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
N = int(input())
D = int(input())
stone_weight_Range = [1,20]
stone_index = list(range(N))
stone_weight=[random.randint(stone_weight_Range[0],stone_weight_Range[1])for i in range(N)]
# 数据分布
plt.figure(figsize=(20, 5))
plt.scatter(stone_index,stone_weight, marker="o")
stone_weight2 = find_same_weight(stone_weight)
find_weight_difference(stone_weight2,D)
1000
10
[find_same_weight]循环次数:1000,时间：0.0s
找到两块石头重量分别为 1 11
找到石头label分别为 [0, 45, 58, 90, 129, 162, 181, 184, 186, 216, 240, 242, 287, 296, 307, 356, 405, 406, 408, 416, 443, 474, 478, 522, 556, 618, 624, 663, 670, 671, 680, 694, 744, 776, 787, 831, 833, 840, 846, 859, 862, 866, 871, 891, 894, 901, 908, 919, 929, 940, 944, 948, 960, 969] [6, 16, 22, 53, 72, 83, 87, 105, 122, 143, 170, 191, 259, 260, 303, 310, 314, 316, 361, 377, 395, 438, 457, 530, 532, 538, 551, 554, 564, 573, 598, 603, 621, 630, 632, 686, 709, 721, 732, 733, 773, 777, 821, 844, 845, 847, 849, 958, 965]
循环次数:5,时间：0.0s
找到两块石头重量分别为 8 18
找到石头label分别为 [7, 63, 73, 91, 110, 124, 136, 141, 146, 175, 179, 190, 213, 250, 270, 280, 330, 334, 339, 357, 374, 388, 461, 471, 476, 491, 496, 509, 528, 582, 616, 664, 673, 689, 696, 697, 711, 715, 799, 801, 810, 811, 883, 897, 925, 935, 938] [8, 56, 98, 177, 188, 192, 196, 226, 228, 275, 278, 299, 311, 372, 422, 431, 455, 497, 498, 524, 541, 550, 597, 599, 606, 608, 620, 627, 653, 666, 699, 701, 749, 767, 769, 770, 789, 816, 826, 865, 900, 913, 947, 973]
循环次数:7,时间：0.0s
找到两块石头重量分别为 19 9
找到石头label分别为 [1, 4, 11, 14, 28, 52, 70, 92, 101, 120, 158, 182, 241, 263, 325, 352, 367, 393, 440, 493, 495, 581, 592, 594, 638, 641, 643, 651, 695, 734, 738, 742, 751, 753, 763, 768, 785, 800, 803, 808, 830, 837, 874, 890, 922, 936, 993] [9, 33, 43, 47, 55, 84, 135, 145, 151, 207, 209, 215, 224, 288, 294, 297, 324, 331, 343, 378, 397, 400, 429, 442, 450, 458, 540, 543, 545, 547, 568, 576, 577, 637, 746, 757, 790, 802, 806, 870, 876, 924, 930, 932]
循环次数:8,时间：0.0s
找到两块石头重量分别为 6 16
找到石头label分别为 [10, 37, 48, 62, 74, 117, 127, 142, 144, 150, 205, 230, 267, 349, 368, 452, 462, 466, 470, 475, 479, 518, 539, 585, 587, 636, 642, 646, 656, 684, 703, 713, 740, 779, 792, 794, 838, 903, 998] [15, 46, 65, 79, 100, 111, 174, 198, 217, 221, 232, 251, 252, 262, 284, 309, 319, 337, 342, 359, 371, 379, 382, 389, 435, 447, 480, 484, 557, 567, 571, 580, 623, 634, 635, 690, 692, 728, 752, 778, 822, 843, 853, 855, 916, 921, 943, 949, 967, 986]
循环次数:11,时间：0.0s
找到两块石头重量分别为 5 15
找到石头label分别为 [18, 26, 36, 95, 97, 112, 116, 130, 206, 220, 225, 271, 283, 318, 333, 340, 370, 392, 399, 404, 409, 415, 454, 519, 525, 535, 542, 562, 565, 596, 614, 615, 617, 661, 718, 725, 730, 754, 772, 775, 788, 809, 834, 839, 873, 885, 912, 914, 928, 968, 970, 985, 994] [19, 21, 23, 24, 42, 66, 69, 86, 89, 119, 139, 160, 163, 178, 197, 235, 254, 265, 268, 302, 321, 341, 366, 376, 394, 417, 420, 424, 430, 465, 477, 511, 515, 521, 574, 605, 612, 625, 626, 644, 647, 649, 665, 679, 691, 716, 727, 736, 747, 758, 791, 797, 814, 827, 856, 877, 902, 937, 951, 956, 961, 971, 978, 980]
循环次数:13,时间：0.0009009838104248047s
找到两块石头重量分别为 20 10
找到石头label分别为 [2, 5, 13, 20, 31, 38, 40, 67, 77, 80, 82, 85, 94, 115, 132, 140, 167, 172, 183, 243, 248, 282, 306, 308, 313, 317, 328, 335, 401, 413, 423, 441, 445, 463, 481, 485, 488, 502, 514, 578, 583, 600, 607, 657, 700, 704, 717, 723, 762, 807, 828, 851, 864, 869, 875, 962] [25, 51, 54, 60, 78, 93, 149, 165, 169, 208, 231, 322, 326, 329, 347, 384, 387, 390, 421, 449, 469, 473, 510, 516, 526, 536, 561, 566, 629, 648, 676, 771, 780, 805, 823, 850, 857, 867, 872, 884, 906, 910, 926, 954, 955, 963, 966, 982, 987, 992, 996]
循环次数:14,时间：0.0009009838104248047s
找到两块石头重量分别为 3 13
找到石头label分别为 [3, 17, 30, 44, 88, 99, 131, 164, 173, 180, 195, 199, 201, 204, 219, 223, 233, 238, 264, 289, 323, 338, 344, 351, 386, 428, 436, 439, 453, 459, 482, 500, 517, 533, 579, 586, 609, 628, 639, 688, 693, 698, 712, 729, 743, 765, 766, 798, 861, 881, 895, 915, 975, 981, 990, 991, 997] [27, 61, 103, 114, 123, 126, 148, 166, 202, 229, 236, 249, 256, 257, 285, 286, 350, 360, 383, 456, 487, 490, 492, 503, 505, 529, 548, 552, 559, 575, 645, 659, 674, 675, 685, 708, 737, 739, 820, 829, 882, 896, 909, 911, 917, 918, 920, 939, 945, 950, 957, 976]
循环次数:15,时间：0.0009009838104248047s
找到两块石头重量分别为 12 2
找到石头label分别为 [12, 35, 71, 81, 106, 107, 118, 125, 137, 159, 187, 218, 234, 239, 273, 291, 298, 332, 353, 354, 362, 373, 380, 410, 433, 451, 460, 468, 489, 508, 520, 527, 544, 549, 555, 560, 569, 570, 588, 590, 660, 681, 687, 705, 722, 741, 755, 759, 774, 793, 804, 812, 819, 825, 841, 905, 934, 953, 972, 984] [34, 57, 133, 138, 147, 154, 211, 253, 255, 261, 274, 346, 355, 358, 365, 381, 391, 396, 407, 414, 418, 425, 446, 472, 483, 494, 512, 537, 546, 553, 591, 593, 595, 602, 604, 611, 622, 655, 667, 707, 710, 720, 782, 786, 860, 868, 887, 889, 923, 927, 979, 999]
循环次数:17,时间：0.0009009838104248047s
找到两块石头重量分别为 7 17
找到石头label分别为 [29, 32, 68, 104, 121, 128, 134, 152, 153, 185, 189, 237, 246, 247, 266, 272, 277, 312, 315, 320, 327, 345, 412, 426, 432, 499, 513, 558, 601, 633, 650, 654, 658, 669, 677, 683, 726, 735, 750, 764, 818, 854, 879, 880, 886, 893, 907, 952, 959, 974] [39, 96, 102, 113, 156, 161, 171, 200, 212, 214, 222, 227, 245, 258, 276, 292, 293, 301, 304, 305, 336, 348, 363, 364, 385, 437, 448, 464, 467, 506, 507, 523, 672, 678, 702, 745, 748, 756, 761, 795, 796, 813, 832, 836, 888, 892, 946, 977, 983]
循环次数:18,时间：0.0009009838104248047s
找到两块石头重量分别为 14 4
找到石头label分别为 [41, 49, 59, 109, 155, 157, 168, 176, 194, 244, 269, 279, 369, 398, 402, 419, 427, 444, 486, 501, 563, 631, 640, 652, 714, 719, 724, 731, 760, 784, 815, 835, 852, 858, 863, 899, 904, 931, 964, 989, 995] [50, 64, 75, 76, 108, 193, 203, 210, 281, 290, 295, 300, 375, 403, 411, 434, 504, 531, 534, 572, 584, 589, 610, 613, 619, 662, 668, 682, 706, 781, 783, 817, 824, 842, 848, 878, 898, 933, 941, 942, 988]
循环次数:20,时间：0.0009009838104248047s
[find_weight_difference]最多循环次数:20,时间：0.0009009838104248047s
方法二
针对石头重量可能重复的情况，将hashmap的value变成list，储存重量相同的石头的label
stone_weight = [1,1,1,1,1,11,11,11,1,11]
D = 10
""" Weight difference"""
s = time.time()
hashmap = {}
for index, weight in enumerate(stone_weight):
another_weight1 = weight + D
another_weight2 = weight - D
if another_weight1 in hashmap:
print("找到两块石头重量分别为 {} {} ".format(another_weight1,weight))
print("找到石头label分别为 {} {} ".format(index,hashmap[another_weight1]))
print("循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
if another_weight2 in hashmap:
print("找到两块石头重量分别为 {} {} ".format(another_weight2,weight))
print("找到石头label分别为 {} {} ".format(index,hashmap[another_weight2]))
print("循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
if weight in hashmap:
hashmap[weight].append(index)
else:
hashmap[weight] = [index]
print("[find_weight_difference]最多循环次数:{},时间：{}s \n".format(index+1,time.time()-s))
输出
找到两块石头重量分别为 1 11
找到石头label分别为 5 [0, 1, 2, 3, 4]
循环次数:6,时间：0.0s
找到两块石头重量分别为 1 11
找到石头label分别为 6 [0, 1, 2, 3, 4]
循环次数:7,时间：0.0s
找到两块石头重量分别为 1 11
找到石头label分别为 7 [0, 1, 2, 3, 4]
循环次数:8,时间：0.0s
找到两块石头重量分别为 11 1
找到石头label分别为 8 [5, 6, 7]
循环次数:9,时间：0.0s
找到两块石头重量分别为 1 11
找到石头label分别为 9 [0, 1, 2, 3, 4, 8]
循环次数:10,时间：0.0s
[find_weight_difference]最多循环次数:10,时间：0.0s
corner cases
| 方法 | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 暴力排序找到所有对插值为D | O（n^2） | O（1） | O（1） | 不稳定 |
| hashmap找到所有对插值为D | O（n+n） | O（n+k） | O（1） | 稳定 |
| hashmap找到所有对插值为D（将hashmap的value变成list） | O（n） | O（k） | O（1） | 稳定 |
