数据流中的中位数

剑指 Offer 41. 数据流中的中位数 - 力扣（Leetcode）

题目要求

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

例子：

1
2
3
4
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

提示：

  • 最多会对 addNum、findMedian 进行 50000 次调用。

思路分析

堆

返回中位数：

  1. 维护两个堆，大根堆和小根堆；
  2. 大根堆存放较小的数值，小根堆存放较大的数值，存放数量两边都为12n{1\over2}n；
  3. 如果是偶数，就将两个堆堆顶元素之和/2.0之后返回;
  4. 如果是奇数，就将大根堆堆顶元素*1.0之后返回；

添加：

  1. 如果插入的是偶数，我们就把元素插入到小根堆，然后把小根堆堆顶的元素放入到大根堆里；
  2. 如果插入的是奇数，我们就把元素插入到大根堆，然后把大根堆堆顶的元素放入到小根堆里；

代码实现

时间O(logn) 空间O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MedianFinder {
    Queue<Integer> min,max;
    /** initialize your data structure here. */
    public MedianFinder() {
        // 初始化
        min = new PriorityQueue<>(); // 小根堆
        max = new PriorityQueue<>((x,y)->(y-x)); // 大根堆

    }
    
    public void addNum(int num) {
        // 如果是偶数
        if(min.size() == max.size()){
            min.add(num); // 放入小根堆
            max.add(min.poll()); // 小根堆堆顶元素添加到大根堆
        }else{
            max.add(num); // 放入大根堆
            min.add(max.poll()); // 大根堆堆顶元素添加到小根堆
        }
    }
    
    public double findMedian() {
        // 如果是偶数
        if(min.size() == max.size()){
            return (min.peek() + max.peek()) / 2.0; // 堆顶元素相加/2.0然后返回
        }else{
            return max.peek() * 1.0; // 直接返回大根堆堆顶元素
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和 - 力扣（Leetcode）

题目要求

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

例子：

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

思路分析

  1. 定义一个dp[i]：以元素nums[i]为结尾的连续子数组最大的和；
  2. 找关系式：dp[i] = max(nums[i],dp[i-1]+nums[i]);
  3. 初始值：dp[0] = nums[0];
  4. 优化：在没刷新dp之前，dp=dp[i-1];在刷新后，dp=dp[i];

代码实现

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 定义一个数组
        dp[0] = nums[0];// 初始值
        int max = nums[0]; // 保存最大值
        for(int i=1;i<nums.length;i++){
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

动态规划+优化

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        // 在没刷新dp之前，dp=dp[i-1]；在刷新后，dp=dp[i];
        int dp = nums[0];// 初始值
        int max = nums[0]; // 保存最大值
        for(int i=1;i<nums.length;i++){
            dp = Math.max(nums[i],dp+nums[i]);
            max = Math.max(max,dp);
        }
        return max;
    }
}

1~n整数中1出现的次数

剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（Leetcode）

题目要求

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

例子：

1
2
3
4
5
输入：n = 12
输出：5
    
输入：n = 13
输出：6

提示：

1 <= n < 2^31

思路分析

例如计算数字位：501222

计算百位上的1

bit就是要求的位，bit左边是high，右边是low；

  • bit=100,cur=(n/bit)%10;
  • low=n%bit,high=n/bit/10;
  • (high+1)*bit(cur>1)

计算千位上的1

  • bit=1000,cur=(n/bit)%10;
  • low=n%bit,high=n/bit/10;
  • (high+1)*bit(cur>1)
  • (high*bit)+(1+1000)(cur=1)

计算万位上的1

  • bit=10000,cur=(n/bit)%10;
  • low=n%bit,high=n/bit/10;
  • (high+1)*bit(cur>1)
  • (high*bit)+(1+1000)(cur=1)
  • high*bit(cur=0)

总结公式：

1
2
3
4
5
6
7
8
9
/*
	cur=(n/bit)%10 
	low = n%bit 
	high = n/bit/10
	
	cur>1 => (high+1)*bit
	cur==1 => (high*bit)+(1+low)
	cur=0 => high*bit
*/

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int countDigitOne(int n) {
        // cur=(n/bit)%10 low = n%bit high = n/bit/10
        // 几个公式
        /*
            cur>1 => (high+1)*bit
            cur==1 => (high*bit)+(1+low)
            cur=0 => high*bit
        */
        long bit = 1;
        int sum = 0;
        while(bit <= n){
            long cur = (n / bit) % 10;
            long low = n % bit;
            long high = n / bit / 10;
            if(cur>1){
                sum +=(high+1)*bit;
            }else if(cur == 1){
                sum +=(high*bit)+(1+low);
            }else if(cur == 0){
                sum += high*bit;
            }
            bit = bit*10;
        } 
        return sum;
    }
}

数字序列中某一位的数字

剑指 Offer 44. 数字序列中某一位的数字 - 力扣（Leetcode）

题目要求

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

例子：

1
2
3
4
5
输入：n = 3
输出：3
    
输入：n = 11
输出：0

提示：

  • 0 <= n < 2^31

思路分析

范围 数字个数 字符个数
bit=1 i=1 1-9 9 9x1=9
bit=10 i=2 10-99 90 90x2=180
bit=100 i=3 100-999 900 900x3=2700
bit=1000 i=4 1000-9999 9000 9000x4=36000
… … … …

例如：n=1000：

  • n>9 => n-9=991;
  • 991>180 => 991-180=811;
  • 811<2700

哪个数：num=bit+(n-1)/i=100+(811-1)/3=100+270=370；

由上可得，第n个字符：index=(n-1)%i+1=(811-1)%3+1=1;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findNthDigit(int n) {
        // 特殊情况
        if(n == 0){
            return 0;
        }
        // 定义变量
        long bit = 1;
        int i = 1;
        long count = 9;
        while(count<n){
            n = (int)(n-count);
            bit = bit*10;
            i++;
            count = bit * i *9;
        }
        // 确定是在哪一个区间的哪个数上
        long num = bit+(n-1)/i;
        // 确定在num的哪个字符
        int index = (n-1)%i+1;
        int res = (int)(num / Math.pow(10,i-index)) %10;
        return res;
    }
}

把数组排成最小的数

面试题45. 把数组排成最小的数 - 力扣（Leetcode）

题目要求

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例子：

1
2
3
4
5
输入: [10,2]
输出: "102"
    
输入: [3,30,34,5,9]
输出: "3033459"

提示：

  • 0 < nums.length <= 100

思路分析

  • 将越小的数字越靠前，位数多的在位数少的前面；
  • 若x=“11”,y=“12”,z=“13”,公式推导：
    • x<y => x+y < y+x;
    • y<z => y+z < z+y;
    • x<z => x+z < z+x;
  • 我们可以使用快速排序来实现；

代码实现

时间O(nlogn) 空间O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public String minNumber(int[] nums) {
        // 定义一个数组
        String [] str = new String[nums.length];
        // 遍历存放到String数组中
        for(int i=0;i<nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        // 快速排序
        quickSort(str,0,str.length-1);
        // 定义StringBuilder
        StringBuilder build = new StringBuilder();
        // 使用 StringBuilder拼接
        for(int i=0;i<str.length;i++){
            build.append(str[i]);
        }
        // 字符串格式返回
        return build.toString();
    }
    // 快速排序，比较那里个快速排序不同
    private void quickSort(String[] arr,int left,int right){
        // 结束条件
        if(left>right){
            return ;
        }
        // 调用partition方法，获取中间元素
        int i = partition(arr,left,right);
        // 递归
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
    // partition方法
    private int partition(String[] arr,int left,int right){
        String pivot = arr[left]; //中间值
        int i=left,j=right;
        while(i<j){
            while(i<=j && (arr[i]+pivot).compareTo(pivot+arr[i])<=0){
                i++;
            }
             while(i<=j && (arr[j]+pivot).compareTo(pivot+arr[j])>=0){
                j--;
            }
            if(i>=j){
                break;
            }
            // 交换
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
}