刷题笔记10—其他经典算法

1 素数筛

非常普遍的，寻找素数可以使用\(O(N^{2})\)复杂度的算法来解决，但是不够高效。下面介绍几种更加高效的寻找素数的算法—素数筛。

最近再看到素数的算法，就想到了6.S081 lab1 中写的 primes 函数，好像其本质就是一个素数筛—埃式筛法

埃式筛法

思路就是，如果一个数是素数，我们可以将这个数的倍数全部划掉，因为它们不可能是素数。

代码如下，当我们找到一个素数时，我们就将这个素数的2倍、3倍、...划掉，而没有被划掉的就是素数。

复杂度：\(O(N loglogN)\)

public int countPrimes(int n) {
    int cnt = 0;
    boolean[] nums = new boolean[n];
    Arrays.fill(nums, true);

    for(int i = 2; i < n; i++){
        if(nums[i]){
            cnt ++;
            for(int j = 2 * i; j < n; j += i){
                nums[j] = false;
            }
        }
    }

    return cnt;
}

但是，很明显这个解法存在一定的冗余，比如说 6 就被素数2 和素数3 重复标记，下面介绍复杂度为\(O(N)\)的线性素数筛

线性筛

线性筛实现了每个合数只被标记一次，时间复杂度为 \(O(N)\)

public int countPrimes(int n) {
    List<Integer> primes = new ArrayList<>();
    boolean[] nums = new boolean[n];
    Arrays.fill(nums, true);

    for(int i = 2; i < n; i++){
        if(nums[i]){
            primes.add(i);
        }
        for(int j = 0; j < primes.size() && primes.get(j) * i < n; j++){
            nums[primes.get(j) * i] = false;
            if(i % primes.get(j) == 0) break;
        }
    }

    return primes.size();
}

2 阶乘

172. 阶乘后的零

这道题很明显直接去算阶乘肯定是行不通的，应该要考虑核心因素。

产生0的原因是阶乘式子中存在\(2 \times 5\)，所以要计算0的数量，只要计算式子中出现了多少对\(2 \times 5\)，即有多少因子2和因子5。

再往下考虑，其实只需要考虑因子5的个数即可，因为因子2在任何偶数中都可以提取出来，所以在一个阶乘式子中，因子2的个数是大于因子5的（可以严格证明）

public int trailingZeroes(int n) {
    int cnt = 0;
    for(int i = n; i / 5 > 0; i /= 5){
        cnt += (i / 5);
    }
    return cnt;
}

793. 阶乘函数后 K 个零

这一题相当于上一题的逆过程。

首先明确，\(f(x)\)肯定是一个单调递增的函数，\(x\)越大，\(f(x)\)的值肯定不会减少。而现在是给定\(f(x)\)，要求出\(x\)，很自然应该使用【二分查找】。

1、注意数据范围：\(k <= 10^9\)，所以能够产生这个\(f(x)\)的\(x\)肯定已经超出了int的范围需要使用long

2、仔细想一想可以发现：给定k之后，要么不存在这样的\(x!\)，如果存在只有5个这样的\(x!\)。

回到上一题的思路，阶乘末尾0的个数 = 阶乘式子中因子5的个数。如果存在的话，应该是能够找到一个\(x\)，是5的倍数，满足\(\le x\)的数中因子5的数量之和\(=k\)。【举个例子，\(k=4\)，存在\(x = 20\)，满足\(\le x\)的数中因子5的数量之和\(=4\)（\(5、10、15、20\)）】既然如此，那么答案应该就在找到的这个\(x\)到下一个5的倍数\(x+5\)之间，即\([x, x+5)\)，因为到下一个5的倍数\(x+5\)时，\(f(x)\)肯定大于\(k\)，所以总共只有5个。

public int preimageSizeFZF(int k) {
    long lo = 0; long hi = Long.MAX_VALUE;
    while(lo <= hi){
        long mid = lo + (hi - lo) / 2;
        long k0 = trailingZeroes(mid);
        if(k0 == k) return 5;
        else if(k0 > k) hi = mid - 1;
        else lo = mid + 1;
    }
    return 0;
}


public long trailingZeroes(long n) {
    long cnt = 0;
    for(long i = n; i / 5 > 0; i /= 5){
        cnt += (i / 5);
    }
    return cnt;
}

3 水塘抽样

这个算法可以实现【低空间复杂度】从无限序列中随机抽取元素。实际上是用时间换空间的一种算法。

问题1：无重复元素

382. 链表随机节点

思路：当遇到第i个元素时，从\([0, i)\)之间随机抽取一个数，如果这个数为0，则将答案置为第i个元素，否则答案不变。这样可以使得返回每个元素的概率都为\(\frac{1}{n}\)。

证明： \[ P(return \ \ i\text{-}th \ \ element) = \\ P(第i次随机选择的值=0) \times P(第i+1次随机选择的值\ne0) \times \cdots \times P(第n次随机选择的值\ne0) =\\ \frac{1}{i} \times (1 - \frac{1}{i+1}) \times (1 - \frac{1}{i+2}) \times \cdots \times (1 - \frac{1}{n}) = \frac{1}{n} \] 代码：getRandom函数的时间复杂度为\(O(N)\)，空间复杂度为\(O(1)\)

class Solution {

    ListNode head;
    Random r;
    
    public Solution(ListNode head) {
        this.head = head;
        r = new Random();
    }
    
    public int getRandom() {
        int i = 0;
        ListNode h0 = head;
        int res = 0;
        while(h0 != null){
            int val = h0.val;
            i++;
            if(r.nextInt(i) == 0){
                res = val;
            }
            h0 = h0.next;
        }
        return res;
    }
}

问题2：存在重复元素

398. 随机数索引

思路：当遇到第i个target时，随机选取\([0, i)\)之间的一个整数，如果其为0，这将答案置为target下标，否则答案不变。如果存在k个target，保证返回每个索引的概率都为\(\frac{1}{k}\)。

证明同上。

代码：pick函数的时间复杂度为\(O(N)\)，空间复杂度为\(O(1)\)

class Solution {

    int[] nums;
    Random r;

    public Solution(int[] nums) {
        this.nums = nums;
        r = new Random();
    }
    
    public int pick(int target) {
        int times = 0;
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                times ++;
                if(r.nextInt(times) == 0){
                    res = i;
                }
            }
        }
        return res;
    }
}

4 吃葡萄

吃葡萄

【要求】三个人中吃的最多的那个人吃得尽量少，就需要尽可能的平均分。当不考虑每个人只能吃两种葡萄的限制，答案应该是\((a+b+c+2)/3\)，就是总和除3向上取整。

但是有"每个人只能吃两种葡萄"的限制就不能这么简单考虑，因为如果出现"其中两种葡萄很少，第三种很多"的情况时，就不一样了。比如\(a =1,\ b=1,\ c=10000\)，这个时候很明显答案就不是\((a+b+c+2)/3\)了，因为只能吃\(a,b\)两种葡萄的人最多只能吃2颗，这种情况下做不到三个人平均分，只能两个人平均分，来实现吃的最多的人吃得尽量少，就是\((c+1)/2\)，即\((max+1)/2\)

那么如何判断属于哪种情况呢？当\(a,b,c\)三者没有相差很大的情况下，很明显\((a+b+c+2)/3 > (max+1)/2\)；而当其中一种水果远大于另外两种时，\((a+b+c+2)/3 < (max+1)/2\)。所以答案应该是\(max( \ (a+b+c+2)/3,\ (\ max(a,b,c) + 1 \ )/2 )\)

代码：

#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int n = 0;
    cin >> n;
    while(n -- > 0){
        int a, b, c;
        cin >> a >> b >> c;
        int max_val = max( max(a, b), c );
        int sum = a + b + c;
        cout << max( (sum+2)/3, (max_val+1)/2 ) << endl;
    }
}

5 同时寻找缺失和重复的元素

645. 错误的集合

注意数组是无序的

首先很常规的方法有【排序】、【哈希】，这些都需要一定空间复杂度。下面谈谈常数空间复杂度的【映射】和【异或】

映射

public int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int dup = -1;
    for(int i = 0; i < n; i++){
        int idx = Math.abs(nums[i]) - 1;
        if(nums[idx] < 0){ // 重复元素
            dup = Math.abs(nums[i]);
        } else {
            nums[idx] *= -1;
        }
    }
    
    int mis = -1;
    for(int i = 0; i < n; i++){
        if(nums[i] > 0){
            mis = i + 1;
        }
    }
    
    return new int[]{dup, mis};
}

异或

public int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int xor = 0;
    for(int num : nums) xor ^= num;
    for(int i = 1; i <= n; i++) xor ^= i;
    // xor = dup ^ mis
    int lowbit = xor & (-xor);

    int num1 = 0; int num2 = 0;
    for(int num : nums){
        if((lowbit & num) == 0){
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    for(int i = 1; i <= n; i++){
        if((lowbit & i) == 0){
            num1 ^= i;
        } else {
            num2 ^= i;
        }
    }

    for(int num : nums){
        if(num == num1){
            return new int[]{num1, num2};
        }
        if(num == num2){
            return new int[]{num2, num1};
        }
    }

    return null;
}

leetcode刷题笔记

#leetcode

刷题笔记10—其他经典算法

http://example.com/2022/11/15/leetcode/刷题笔记10（其他经典算法）/

作者

zhc

发布于

2022年11月15日

许可协议

刷题笔记9-dp应用上一篇

TypeScript 下一篇