ARTS #63 | 早就是优势

Algorithm

本周选择的算法题是：Count of Smaller Numbers After Self

规则如下：

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Constraints:

0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution

分析后发现从右往左遍历更容易得到答案，具体来说就是从右往左进行排序，这样一来问题就减化成了如何快速找到一个数字的位置，很自然就用了 right-most 的二分查找：

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        arr, ans = [], [0] * len(nums)
            
        def right_most(target: int):
            left, right = 0, len(arr)
            while left < right:
                index = (left + right) // 2
                if arr[index] >= target:
                    right = index
                else:
                    left = index+1
            return left

        for i in range(len(nums)-1, -1, -1):
            curr = nums[i]
            inserted_index = right_most(curr)
            if inserted_index == len(arr):
                ans[i] = len(arr)
                arr.append(curr)
            else:
                ans[i] = inserted_index
                arr.insert(inserted_index, curr)
        return ans

该方法的执行情况如下：

执行用时：132 ms, 在所有 Python3 提交中击败了95.11%的用户
内存消耗：15.6 MB, 在所有 Python3 提交中击败了97.73%的用户

同样是排序，评论区大佬有更好的策略：

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        ans = [0] * len(nums)
        def merger_sort(enums: List[int]):
            half = len(enums) // 2
            if half:
                left, right = merger_sort(enums[:half]), merger_sort(enums[half:])
                for index in range(len(enums)-1,-1,-1):
                    if not right or left and left[-1][1] > right[-1][1]:
                        ans[left[-1][0]] += len(right)
                        enums[index] = left.pop()
                    else:
                        enums[index] = right.pop()
            return enums
        merger_sort(list(enumerate(nums)))
        return ans

归并排序思想，代码紧凑，非常好的思路！

Review

Data Visualization

这是一家商业公司写的关于数据可视化的文章。

什么是数据可视化？

将数据进行采集、处理和模型化，然后把数据之间的复杂关系提炼成可视化的图形，以便得出结论。整个过程就是数据可视化。

它为什么重要？

主要是因为当今社会生产的数据太多了，目前整个世界每天生产2.5亿字节的数据，并且90%的数据是过去近两年时间生产的，这么多数据的管理、理解难度可想而知。

文章中的例子图如下：

传统的方式：
数据可视化之折线图：

后者更直观，如果表格中有成千上万条记录，虽然最终也能得出相同的结论，但是早，早就是优势，商业社会尤其如此，能帮助分析员、公司比竞争对手更快地做出决策就相当有价值。

更多内容见原文，有数据可视化发展的简史，各个图表的功能、受众等详细介绍。

Tip

为了解决安卓 CI 环境更新部署的问题，尝试将 sdk、ndk、环境变量以及其他依赖做了一份 docker 镜像，经过测试+观察后可以满足预期。

Python 与 OC 内存管理的差异简要：

两者都是引用计数为主的策略，除此之外 Python 引入了 GC 来解决循环引用的问题
- Python 使用类似于标记-清除算法来处理循环引用：
  - 标记 - 遍历所有对象，通过对计数-1来测试它们的可达性
  - 清除 - 如果一个对象没有被标记为可达，则将其回收
- Python 为了优化 GC 效率，引入了分代回收
iOS 不支持 GC，不过早期的 OS X 系统是支持 GC 的：
- 10.5 通过 NSGarbageCollector 实现 GC，直到 10.8 被废弃
- 同 stop-the-world 不同，OC 的 GC 工作在一个低优先级的后台线程，并且它会在接收用户事件时中断，以快速响应用户的操作
关于 Python 的具体 GC 策略见这篇的 Review 部分

Algorithm

Solution

Review

什么是数据可视化？

它为什么重要？

Tip

Share