ARTS 第 8 周

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Algorithm

难度：Easy

题意：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [ n/2 ] 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

示例一：

Input: [3,2,3]
Output: 3

示例二：

Input: [2,2,1,1,1,2,2]
Output: 2

解法一，暴力循环：暴力算法遍历整个数组，然后再次遍历每一个元素来统计它出现的次数，一旦一个元素出现次数大于 [ n/2 ]，即返回它。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        majority_count = len(nums)//2
        for num in nums:
            count = sum(1 for elem in nums if elem == num)
            if count > majority_count:
                return num

时间复杂度为 O(n2)，空间复杂度为 O(1)。

这个解法有一点需要注意，就是在第二次循环的时候，使用了生成器来统计元素的出现次数，这可以减少内存的使用。

解法二，使用哈希表：在 Python 中，我们可以使用 collections 中的 Counter 来统计元素出现的次数。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

时间复杂度为 O(n)，空间复杂度为 O(n)。

解法三，排序法：因为该题规定众数出现次数大于 [ n/2 ]，所以如果将数组排序，那么中间的一个元素一定是那个众数。在 Python 中，我们可以很容易使用 sort 来对数组进行排序。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[len(nums)//2]

时间复杂度为 O(nlogn)，空间复杂度为 O(1)（如果原地排序数组是可行的话）或者 O(n)（如果原地排序数组不可行）。

Review

Cyber Insects

这周读了一篇简短的文章，讲的是人造智能昆虫将如何从军事和农业两方面影响人类生活的。

其实大部分先进的科学技术首先都是被用于军事方面，基本上我们现在才开始使用的大部分的不可思议的事物，其实很早就被创造并应用于军事工业了。人造昆虫就是其中一个例子。在军事方面，人造昆虫被用于监视敌人、破坏无线电台、损坏线路和网络等。更为重要的是，人工智能为这些人造昆虫提供了升级能力的可能，这让他们能够躲避动物的攻击、远离人类、从复杂困难的环境中逃离以及像普通昆虫一样行动。

另外一方面，人造昆虫还能够被用于农业，能够极大的减少农业生产中的人力参与。人造昆虫可以被用于播种、对抗害虫、监控播种并汇报种子发芽的质量等等。

We’re making this analogy that AI is the new electricity. Electricity transformed industries: agriculture, transportation, communication, manufacturing.

不过这篇文章关于人造昆虫在军事上的应用让我想起了之前杀手机器人视频引起的恐慌。可以参考这个链接：https://www.youtube.com/watch?v=TlO2gcs1YvM。

Tips

推荐几个 Vim 插件

Goyo
vim-startify
vim-airline
indentLine

Python 中的生成器

由于今天在 Algorithm 中又见到了生成器的身影，遂决定把生成器研究透彻。

这里分享一篇「Python 之禅」的文章《看完这篇，你就知道Python生成器是什么》，我个人觉得讲得非常的透彻易懂，重要的一点是「本质上 for 循环也是调用 next 方法」。

ARTS 第 8 周

Contents:

Algorithm

Review

Tips

Share