题目分析

本题是172题的扩展，其实难度仅比172高一点点，勉强算一个困难题，根据题目中k的范围，提示很明显应该使用**O(1)的算法或者O(log(n))**的算法，小伙伴们想一想叭。

二分查找

我们分析，记f(x)是x的阶乘后面0的个数，可以知道f(x)单调递增函数，满足
$$ f(x + 1) \ge f(x) $$

因此我们要计算f(x) = k的最小索引m，然后再计算f(x) = k + 1的最小索引n，最后的结果就是n - m。

我们可以使用二分的方式求解f(x) = k中符合条件的最小索引。

f(x)是阶乘后面0的个数，如何迅速求解一个数的阶乘后面有多少个0呢？

这又运用到了数学知识，我们知道有多少个0，就说明有多少个10，而10又可以拆分成2和5，且2的个数一定大于5，所以我们只需要看x的阶乘中，可以拆分出多少个5，即有多少个0。

现在还有一个问题，是不是x的阶乘里面就有x / 5个5呢？答案是错误的，因为25、50、75、100中含有2个5，125、250…含有3个5。

所以x / 5仅仅获取到是5的倍数的元素数量，对于25、50、75、100…来说还需要获取是25的倍数的元素数量，因为统计5的倍数的元素数量时已经考虑到25的倍数了，因此需要再加x / 25。125、250…依次类推。x阶乘里面5的个数有x / 5 + x / 25 + x / 125 + …

算法的时间复杂度为$ O(log^{2}k) $，空间复杂度为O(1)。

class Solution {
    public int preimageSizeFZF(int k) {
        return getMinIndex(k + 1) - getMinIndex(k);
    }
    
    private int getMinIndex(int k) {
        int left = 0;
        int right = 5 * k;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (getZero(mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private int getZero(int x) {
        int res = 0;
        while (x != 0) {
            x /= 5;
            res += x;
        }
        return res;
    }
}

刷题总结

有的困难题也并不是很难，小伙伴们不用太害怕，千万不能看到hard就放弃。