开始刷题吧！十道腾讯金三银四高频leetcode算法题分享（附解题思路及实现代码！）_10亿个数中如何高效地找到最大的一个数以及最大的第 k 个数

1.最大子序和

方法一：动态规划

思路和算法

假设 nums 数组的长度是 n，下标从 0 到 n−1。

我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

不难给出一个时间复杂度 O(n)、空间复杂度 O(n) 的实现，即用一个 f 数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i) 只和 f(i−1) 相关，于是我们可以只用一个变量 pre 来维护对于当前 f(i) 的 f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动数组」的思想。

class Solution {
   
    public int maxSubArray(int[] nums) {
   
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
   
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度

• 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

2.10亿个数中如何高效地找到最大的一个数以及最大的第 K 个数

1. 10亿个数中如何高效地找到最大的一个数

将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的那个数据，最后在剩下的1000个数据里面找出最大的数据。 从100万个数据遍历选择最大的数，此方法需要每次的内存空间为10^6*4=4MB，一共需要1000次这样的比较。

2. 10亿个数中如何高效地找到第K个数

• 对于top K类问题，通常比较好的方案是分治+hash+小顶堆：
  • 先将数据集按照Hash方法分解成多个小数据集
  • 然后用小顶堆求出每个数据集中最大的K个数
  • 最后在所有top K中求出最终的top K。
• 如果是top词频可以使用分治+ Trie树/hash +小顶堆：
  • 先将数据集按照Hash方法分解成多个小数据集
  • 然后使用Trie树或者Hash统计每个小数据集中的query词频
  • 之后用小顶堆求出每个数据集中出频率最高的前K个数
  • 最后在所有top K中求出最终的top K。
• 时间复杂度：建堆时间复杂度是O(K),算法的时间复杂度为O(NlogK)。

3. top K常用的方法

• 快排+选择排序：排序后的集合中进行查找
  • 时间复杂度： 时间复杂度为O(NlogN)
  • 缺点：需要比较大的内存，且效率低
• 局部淘汰：取前K个元素并排序，然后依次扫描剩余的元素，插入到排好序的序列中(二分查找)，并淘汰最小值。
  • 时间复杂度： 时间复杂度为O(NlogK) (logK为二分查找的复杂度)。
• 分治法：将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的K个，最后在剩下的1000*K个数据里面找出最大的K个，100万个数据里面查找最大的K个数据可以使用Partition的方法
  • 时间复杂度： 时间复杂度为O(N+1000*K)
• Hash法： 如果这10亿个数里面有很多重复的数，先通过Hash法，把这10亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的K个数。
• 小顶堆： 首先读入前K个数来创建大小为K的小顶堆，建堆的时间复杂度为O(K)，然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。
  • 时间复杂度： 时间复杂度为O(NlogK)
• Trie树： 如果是从10亿个重复比较多的单词找高频词汇，数据集按照Hash方法分解成多个小数据集，然后使用Trie树统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
  • 适用范围：数据量大，重复多，但是数据种类小可以放入内存
  • 时间复杂度：O(Len*N)，N为字符串的个数,Len为字符串长度
• 桶排序：一个数据表分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。
  • 使用范围：如果已知了数据的范围，那么可以划分合适大小的桶，直接借用桶排序的思路
  • 时间复杂度：O(N*logM)，N 为待排序的元素的个数，M为桶的个数
• 计数排序：计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
  • 适用范围：只能用在数据范围不大的场景
  • 时间复杂度：O(N)
• 基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。
  • 适用范围：可以对字符串类型的关键字进行排序。
  • 时间复杂度： O(N*M)，M为要排序的数据的位数

4. 实际情况

（1）单机+单核+足够大内存

• 顺序遍历（或先用HashMap求出每个词出现的频率）
  • 查找10亿个查询次（每个占8B）中出现频率最高的10个，考虑到每个查询词占8B，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存，直接在内存中对查询次进行排序，顺序遍历找出10个出现频率最大的即可。
  • 优点： 简单快速

（2）单机+多核+足够大内存

• partition + （1）
  • 直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。
  • 瓶颈：数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程。
  • 解决的方法：将数据划分成c×n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，知道所有数据处理完毕，最后由一个线程进行归并。

（3）单机+单核+受限内存

• 分治 + （1）
  • 将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，直到每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。

（4）多机+受限内存

• 数据分发 + （3）
  • 将数据分发到多台机器上，每台机器采用（3）中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
• MapReduce
  • top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce 函数，然后提交到Hadoop
    • 首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。
    • 得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。
    • 对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。

3.爬楼梯

第一种思路

标签：数学

如果观察数学规律，可知本题是斐波那契数列，那么用斐波那契数列的公式即可解决问题，公式如下：

• 时间复杂度：O(logn)

第一种思路代码

class Solution {
   
    public int climbStairs(int n) {
   
        double sqrt_5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
        return (int)(fib_n / sqrt_5);
    }
}
1
2
3
4
5
6
7
8
9

第二种思路

标签：动态规划

本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和

1. 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
2. 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶

所以我们得到公式 dp[n]=dp[n−1]+dp[n−2]
同时需要初始化 dp[0]=1 和 dp[1]=1
时间复杂度：O(n)

第二种思路代码

class Solution {
   
    public int climbStairs(int n) {
   
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
   
            dp[i] 
1
2
3
4
5
6
7
8
9