我们公司对不忠的员工是零容忍。老大说了:看到谁在招聘网站上活跃了，第一时间告诉我，立马换人

公司嘴上喊“对不忠员工零容忍”，这话一出来，味儿就不对了。更离谱的是，老板还亲自下指令：谁在招聘网站上活跃，马上汇报，立马换人。听着像抓内鬼，实际上跟宿舍查手机没啥区别。

问题是，你要真是神仙公司，谁没事天天刷招聘软件？现在这行情，多少人上班跟开盲盒似的，工资、活儿、气氛，哪个都不稳。90%以上的人都有想走的念头，这已经不是员工“不忠”了，这是公司自己把人心干散了。

我看这事最逗的地方就在这儿：一个公司天天防员工跑，本身就说明留人这事早就做砸了。真有本事的老板，盯的是怎么让人不想走，不是盯谁偷偷改了简历。

招聘部干久了，估计看见“活跃状态”四个字，眼皮都跳。

算法题：计算右侧小于当前元素的个数

数组里最烦的一类题，不是不会写，是第一眼看上去像双层循环，真写出来也能过小数据，一上规模就直接超时。

“计算右侧小于当前元素的个数”就是这种题。 比如 nums = [5,2,6,1]，答案是 [2,1,1,0]。5 右边比它小的有 2 和 1，2 右边只有一个 1，6 右边也只有一个 1。

很多人上来就是这么写：

defcount_smaller(nums):
    ans = []
    n = len(nums)
for i in range(n):
        cnt = 0
for j in range(i + 1, n):
if nums[j] < nums[i]:
                cnt += 1
        ans.append(cnt)
return ans

逻辑没毛病，问题也很直接：O(n^2)。数据一大，这种写法我一般都不太信。算法题里只要出现“右侧有多少个比当前小”，十有八九不是让你老老实实数，而是让你在“排序”的过程中把这个数顺手带出来。

这题我更愿意用归并排序来做。

归并排序有个很顺手的地方：左半部分和右半部分在合并之前，各自已经有序。那当左边某个数要落位时，右边已经有多少个更小的数被提前放进结果里，这个数量其实就能直接记到账上。

核心不是排出序，而是借着“谁先合并”这件事统计答案。

defcount_smaller(nums):
    n = len(nums)
    ans = [0] * n
    arr = list(enumerate(nums))  # (原下标, 值)

defmerge_sort(left, right):
if left >= right:
return

        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid + 1, right)

        tmp = []
        i, j = left, mid + 1
        right_count = 0

while i <= mid and j <= right:
if arr[j][1] < arr[i][1]:
                tmp.append(arr[j])
                right_count += 1
                j += 1
else:
                idx = arr[i][0]
                ans[idx] += right_count
                tmp.append(arr[i])
                i += 1

while i <= mid:
            idx = arr[i][0]
            ans[idx] += right_count
            tmp.append(arr[i])
            i += 1

while j <= right:
            tmp.append(arr[j])
            j += 1

        arr[left:right + 1] = tmp

    merge_sort(0, n - 1)
return ans

拿 [(0,5),(1,2),(2,6),(3,1)] 这组数据看，合并 [5,2] 和 [6,1] 的过程中，右边的小数一旦先出队，right_count 就加一。后面左边元素再放进去时，这个计数就说明：它右边已经有多少个更小的元素跑到它前面去了。

这地方容易错两个点。

一个是相等怎么处理。题目要的是“更小”，不是“小于等于”，所以判断必须写成：

if arr[j][1] < arr[i][1]:

不能手滑写成 <=。这个地方一改，重复元素的结果就全乱了。

另一个是你不能只排值，必须把原始下标带着。因为最后答案要按原数组位置回填，不是按排序后的位置给。

简单跑一下：

print(count_smaller([5, 2, 6, 1]))   # [2, 1, 1, 0]
print(count_smaller([-1]))           # [0]
print(count_smaller([-1, -1]))       # [0, 0]

时间复杂度是 O(n log n)，空间复杂度 O(n)。这才是这题该有的样子。