Vincent 原创 2023-03-24

算法教程第一天，数据结构-数组，python操作数组，快点学起来！！！-【原创】

一、为什么要学算法

相信很多半路出家或是没接受系统学习算法的程序员都会和我刚入职那会一样，都有一个疑问，就是为什么要学习算法，学习算法到底有什么用？那这里我举个简单例子，让大家感受一下算法的魅力：

# 请计算1+2+3+4+...+100=?
#方法1:依次累加
sum = 0
for i in rang(101):
    sum += i
#方法2:求和公式 n*(n+1)/2
sum = 100*101/2

很明显我们可以发现，方法1原本需要计算100次，方法2一次计算就解决了，这里我们假设要计算n个数的累加和，那么方法1我们就要计算n次，在计算机科学中，我们通常使用时间复杂度（常用大O符号表述），定性的描述该算法的运行时间，这里方法1的时间复杂度我们记做O(n)，算法2我们记做O(1)，很明显O(1)所需的时间是很少的，这里给出一张大O复杂度图表，大家可以感受一下，优秀算法在我们代码中是多么的必要且重要！如果你现在还在一直不加思考的写代码，不关心代码的时间复杂度，这是多么可怕的一件事！

二、怎么学算法

2.1 三分学七分练

算法的学习除了掌握基本的概念知识，还要不停的去练习，练习，练习！！！直至熟能生巧，举一反三。

这里练习，我会挑选leetcode的算法题目，有针对性的去练，逐步分析，先自己写，再去看优秀的代码，看看自己与别人的差距在哪，然后再去练习。

三、数组（Array）

3.1 定义

数组是内存中连续的一段存储区域，数据拥有自己的下标（这样计算机就可轻而易举去访问数据）

3.2 时间复杂度

因为数组具有连续性，所以在查找，插入，删除时时间复杂度都为O(n)

3.3 python操作数组

class ArrayTest:
    def test(self):
        # Create an array
        a = []
        # Add element
        # Time Complexity: O(1)
        a.append(1)
        a.append(2)
        a.append(3)
        # [1,2,3]
        print(a)
        # Insert element
        # Time Complexity: O(N)
        a.insert(2, 99)
        # [1,2,99,3]
        print(a)
        # Access element
        # Time Complexity: O(1)
        temp = a[2]
        # 99
        print(temp)
        # Uodate element
        # Time Complexity: O(1)
        a[2] = 88
        # [1,2,88,3]
        print(a)
        # Remove element
        # Time Complexity: O(N)
        a.remove(88)
        # [1,2,3]
        print(a)
        a.pop(1)
        # [1,3]
        print(a)
        # Time Complexity: O(1)
        a.pop()
        # [1]
        print(a)
        a = [1, 2, 3]
        # Get array size
        size = len(a)
        # 3
        print(size)
        # Iterate array
        # Time complexity: O(N)
        for i in a:
            print(i)
        for index, element in enumerate(a):
            print(f"Index at {index} is: {element}")
        for i in range(0, len(a)):
            print(f"i: {i} element: {a[i]}")
        # Find an element
        # Time complexity: O(N)
        index = a.index(2)
        # 1
        print(index)
        # Sort an array
        # Time Complexity: O(NlogN)
        # From small to big
        a = [3, 1, 2]
        a.sort()
        # [1,2,3]
        print(a)
        # From big to small
        a.sort(reverse=True)
        # [3,2,1]
        print(a)

if __name__ == "__main__":
    test = ArrayTest()
    test.test()

四、练习

4.1 LeetCode 485题

思路

为了得到数组中最大连续 1的个数，需要遍历数组，并记录最大的连续 1 的个数和当前的连续 1 的个数。如果当前元素是 1，则将当前的连续 1 的个数加 1，否则，使用之前的连续 1 的个数更新最大的连续 1 的个数，并将当前的连续 1 的个数清零。

遍历数组结束之后，需要再次使用当前的连续 1 的个数更新最大的连续 1 的个数，因为数组的最后一个元素可能是 1，且最长连续 1 的子数组可能出现在数组的末尾，如果遍历数组结束之后不更新最大的连续 1的个数，则会导致结果错误。

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        maxCount = count = 0

        for i, num in enumerate(nums):
            if num == 1:
                count += 1
            else:
                maxCount = max(maxCount, count)
                count = 0

        maxCount = max(maxCount, count)
        return maxCount