数据结构python实现之动态数组

(一)Introduction

引入问题:找到丢失的数字

数据结构python实现之动态数组

算法实现1:求和相减

算法实现2:异或运算

A^A=0
A^0=A
A^B=B^A
========================================
(1^2^3...x^...n)^
(1^2^3...0^...n)
---------------
0^0^0...x^...0=x

1. 时间复杂度与空间复杂度

O(1) < O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(n!)

2. 主项定理

T(n):解决这个问题所花的时间

aT(n/b):每个大问题可以分解成a个小问题(所需要的小问题的个数),每个小问题的size为n/b

f(n):每一步的时间
数据结构python实现之动态数组

二分法的主项公式:T(n) = T(n/2) + 1

归并排序:T(n) = 2T(n/2) + n

(二)Array

1. Array的应用

(1)洗牌

算法1:每次产生两张牌,任意交换其位置

def shuffle_1st(cards):
    for k in range(len(cards)):
        i = random.randint(0,len(cards)-1)
        j = random.randint(0,len(cards)-1)
        cards[i],cards[j] = cards[j],cards[i]

def test_shuffle(f):
    results = [[0 for i in range(10)] for j in range(10)]

    for i in range(10000):
        A = [i for i in range(0,10)]
        f(A)
        print(A)
        for j in range(len(A)):
            results[A[j]][j] += 1

    print('\n'.join([''.join(['{:6}'.format(item) for item in row])for row in results]))


test_shuffle(shuffle_1st)
----------------------------results--------------------------------------
  1949   878   889   895   892   903   910   876   889   919
   841  2051   846   931   839   945   887   856   884   920
   930   881  2036   884   865   857   893   872   928   854
   888   814   922  1979   940   894   891   882   893   897
   865   896   901   891  1943   875   928   916   881   904
   905   927   869   885   912  1911   904   902   890   895
   900   857   895   911   921   931  1936   876   884   889
   940   873   890   883   851   876   893  2010   886   898
   894   902   890   859   915   848   876   879  2023   914
   888   921   862   882   922   960   882   931   842  1910

明显对角线元素数量最多,也就是第i张牌在第i个位置的概率最大,显然并不是一个很好的洗牌算法。

算法2:每次产生一张牌i,让这张牌和第k次对应的第k张牌进行交换

def shuffle_2nd(cards):
    for k in range(len(cards)):
        i = random.randint(0,len(cards)-1)
        cards[k],cards[i] = cards[i],cards[k]

def test_shuffle(f):
    results = [[0 for i in range(10)] for j in range(10)]

    for i in range(10000):
        A = [i for i in range(0,10)]
        f(A)
        print(A)
        for j in range(len(A)):
            results[A[j]][j] += 1

    print('\n'.join([''.join(['{:6}'.format(item) for item in row])for row in results]))


test_shuffle(shuffle_2nd)
----------------------------results--------------------------------------
  995   982  1004  1018  1022  1039  1003   953   995   989
  1264   956   906   939   979   909   992  1019  1008  1028
  1148  1301   905   880   971   925   973   921   967  1009
  1111  1156  1199   932   895   917   922   933   944   991
  1095  1037  1185  1158   844   891   881   945   983   981
   973  1029  1100  1141  1151   847   884   953   977   945
   936   977   975  1038  1089  1204   858   930   995   998
   842   879   953  1011  1093  1137  1230   895   971   989
   806   889   904   964   973  1094  1177  1238   932  1023
   830   794   869   919   983  1037  1080  1213  1228  1047

明显对角线元素数量最多少,也就是第i张牌在第i个位置的概率最小,显然并不是一个很好的洗牌算法。

算法3:

每次随机产生一张牌从本次循环靠后的一张牌,然后和本张牌进行交换,即每次之后自己以及自己之后的任意一张牌进行交换,每张牌在每个位置的概率为1/n

def shuffle_correct(cards):
    for k in range(len(cards)):
        randomi = random.randint(k,len(cards)-1)
        cards[k],cards[randomi] = cards[randomi],cards[k]

def test_shuffle(f):
    results = [[0 for i in range(10)] for j in range(10)]

    for i in range(100000):
        A = [i for i in range(0,10)]
        f(A)
        print(A)
        for j in range(len(A)):
            results[A[j]][j] += 1

    print('\n'.join([''.join(['{:6}'.format(item) for item in row])for row in results]))


test_shuffle(shuffle_correct)
----------------------------results-----------------------------------------
  9967  9951  9888 10069 10070  9963  9972 10031 10130  9959
  9898 10034 10126 10102 10072  9948  9819 10007  9967 10027
  9949 10009  9883 10009  9826 10074  9991 10047  9980 10232
 10090 10063 10025 10070  9943  9886 10132  9832  9932 10027
 10028  9933  9951  9991  9980 10205 10012  9790 10061 10049
 10099  9856  9939 10111 10019  9931  9879 10224 10017  9925
  9931 10094 10038  9941  9957 10006 10032  9985  9900 10116
  9915  9994 10070  9864 10071 10105  9945 10137  9953  9946
 10097 10085 10039  9958 10056  9879  9954 10005 10067  9860
 10026  9981 10041  9885 10006 10003 10264  9942  9993  9859

(2)计算素数

计算比n小的指数的个数(用空间换时间的思路)

def count_prime(n):
    is_prime = [True] * (n + 1)
    i = 2
    while i * i <= n:
        if (is_prime[i]):
            j = i
            while (j * i <= n):
                is_prime[i * j] = False
                j += 1
        i += 1
        
    count = 0
    for i in range(2, n+1):
        if is_prime[i]:
            count += 1
            print(i, end = " ")
            
    return count

(3)哥德巴赫猜想

任一大于2的偶数,都可表示成两个质数之和。

def goldbach(n):
	#find all prime
    is_prime = [True] * (n + 1)
    i = 2
    while i * i <= n:
        if is_prime[i]:
            j = i
            while (j * i <= n):
                is_prime[i * j] = False
                j += 1
        i += 1
    
    #calc amount of prime
    count = 0
    for i in range(2, n+1):
        if is_prime[i]:
            count += 1
            
    #two pointer        
    primes = [None] * count
    idx = 0
    for i in range(2, n + 1):
        if is_prime[i]:
            primes[idx] = i
            idx += 1
    
    left = 0
    right = count - 1
    while left < right:
        if n == primes[left] + primes[right]:
            print(n," = ", primes[left], " + ", primes[right])
            left += 1
            right -= 1
        elif n > primes[left] + primes[right]:
            left += 1
        else:
            right -= 1

2.动态数组

  • 创建空列表
  • 确定此列表是否为空
  • 确定列表中元素个数
  • 给列表中给定位置添加元素
  • 在列表中给定位置删除元素
  • 删除列表中的所有元素
  • 获取列表中给定位置的元素

动态数组的简单实现:

import ctypes


class DynamicArray:

    def __init__(self):
        'Create an empty array'
        self._size = 0
        self._capacity = 10
        self._eles = self._make_array(self._capacity)

    def __len__(self):
        return self._size
    
    def is_empty(self):    
        return self._size == 0
    
    def __getitem__(self, index):
        if not 0 <= index <self._size:
            raise ValueError("Invalid index")
        return self._eles[index]
    
    def append(self,item):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)     
        self._eles[self._size] = item
        self._size += 1
            
    def insert(self,index,item):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        for k in range(self._size,index,-1):
            self._eles[k] = self._eles[k-1]
        self._eles[index] = item 
        self._size += 1
        
    def remove(self,value):
        for i in range(self._size):
            if self._eles[i] == value:
                for j in range(i,self._size-1):
                    self._eles[j] = self._eles[j+1]
                self._eles[self._size-1] = None    
                self._size -= 1
                return 
        raise ValueError("value not found")
    
    def print(self):
        for i in range(self._size):
            print(self._eles[i],end=' ')
        
    def _resize(self,capacity):
        new_array = self._make_array(capacity)
        for k in range(self._size):
            new_array[k] = self._eles[k]
        self._eles = new_array
        self._capacity = capacity
        
    def _make_array(self,capacity):
        return (capacity * ctypes.py_object)()
上一篇:适用于Bash编程初学者小例子 - 第一篇


下一篇:制作数据集(二):使用Bing,制作更快,更干净的数据集!