Java之差分算法

小鱼儿 2024-03-26 12:50 60阅读 0赞

**目录**

一.差分

1.什么是差分

2.差分数组所解决的问题

3.差分解题的步骤

4.举例差分解题

二.小明的彩灯

1.题目描述

题目描述

输入描述

输出描述

2.问题分析

3.代码实现

三.人口最多的年份

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.差分 ##

### 1.什么是差分 ###

差分的概念:有一列数字:**如:a\[0\],a\[1\],a\[2\],.....a\[n\]**,它的每一项与前边一项进行**相减**的操作

例如差分数组**:b\[0\]=a\[0\],b\[1\]=a\[1\]-a\[0\],b\[2\]=a\[2\]-a\[1\],.......,b\[n\]=a\[n\]-a\[n-1\]**  类似于这样的操作就叫做差分

### 2.差分数组所解决的问题 ###

差分数组主要用于解决:对某些**不确定的区间**多次进行**加减操作**时，如果每次都是对这些区间遍历操作,(设进行**n次操作**,每次对**长度为m的数组**进行操作),时间复杂度为O(nm),如果使用差分来进行解决的话,可以将时间复杂度变为O(n)

注意:差分**只能够解决加减**的问题,**不能够解决乘除**的问题

### 3.差分解题的步骤 ###

**1.构造差分数组: 数组为:a\[0\],a\[1\],a\[2\],.....a\[n\]**

**那么差分数组为:b\[0\]=a\[0\],b\[1\]=a\[1\]-a\[0\],b\[2\]=a\[2\]-a\[1\],.......,b\[n\]=a\[n\]-a\[n-1\]**

**2.进行相对应的加减操作(例如,需要对left到right个元素全部加x,b\[left\]+=x,b\[right\]-=x)**

**3.差分还原(进行求前缀和的操作)**

**a\[0\]=b\[0\], a\[1\]=b\[1\]+a\[0\],a\[2\]=a\[1\]+b\[2\]**

### **4.举例差分解题** ###

**对于数组nums=\{1,2,4,6,7,9\},将第2到第4个元素加3,第3到第5个元素减1,求操作后的数组**

**1.构造差分数组**

**diff\[0\]=nums\[0\]=1 diff\[1\]=nums\[1\]-nums\[0\]=1 diff\[2\]=nums\[2\]-nums\[1\]=2**

**diff\[3\]=nums\[3\]-nums\[2\]=2 diff\[4\]=nums\[4\]-nums\[3\]=1 diff\[5\]=nums\[5\]-nums\[4\]=2**

**diff=\{1,1,2,2,1,2\}**

**2.进行相应操作**

**进行加3操作: diff\[1\]+=3 diff\[4\]-=3; diff=\{1,4,2,2,-2,2\}**

**进行减1操作: diff\[2\]-=1 diff\[5\]+=1 diff=\{1,4,1,2,-2,3\}**

**3.差分数组的还原**

**nums\[0\]=diff\[0\]=1 nums\[1\]=diff\[1\]+nums\[0\]=5 nums\[2\]=diff\[2\]+nums\[1\]=6**

**nums\[3\]=diff\[3\]+nums\[2\]=8 nums\[4\]=diff\[4\]+nums\[3\]=6 nums\[5\]=diff\[5\]+nums\[4\]=9**

**nums=\{1,5,6,8,6,9\}**

## **二.小明的彩灯** ##

### **1.题目描述** ###

> #### 题目描述 ####
> 
> 小明拥有 N 个彩灯，第 i 个彩灯的初始亮度为 ![a\_\{i\}][a_i]。
> 
> 小明将进行 Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。
> 
> 求 Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。
> 
> #### 输入描述 ####
> 
> 第一行包含两个正整数 N，Q 分别表示彩灯的数量和操作的次数。
> 
> 第二行包含 N 个整数，表示彩灯的初始亮度。
> 
> 接下来 Q 行每行包含一个操作，格式如下：
> 
> `l r x`，表示将区间 l∼r 的彩灯的亮度 +x。
> 
> #### 输出描述 ####
> 
> 输出共 1 行，包含 N 个整数，表示每个彩灯的亮度。

### **2.问题分析** ###

**这道问题是典型的差分问题,我们只需要按照上面的三步进行实现即可**

### **3.代码实现** ###

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) throws IOException{
            //在此输入您的代码...
            StreamTokenizer sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            sc.nextToken();
            int n=(int)sc.nval;
            sc.nextToken();
            int q=(int)sc.nval;
            long[] light=new long[n+1];
            long[] diff=new long[n+1];
            for(int i=1;i<=n;++i){
              sc.nextToken();
              light[i]=(long)sc.nval;
              diff[i]=light[i]-light[i-1];
                     
            }
            for(int i=0;i<q;++i){
              sc.nextToken();
              int left=(int)sc.nval;
              sc.nextToken();
              int right=(int)sc.nval;;
              sc.nextToken();
              int add=(int)sc.nval;
                diff[left] += add;
                if(right<n)
                diff[right+1] -= add;
            }
            
            for(int j=1;j<=n;j++)
            light[j]=light[j-1]+diff[j];
            for(int i=1;i<=n;++i){
              if(light[i]<0) light[i]=0;
              System.out.print(light[i]+" ");
            }
            
        }
    }

## 三.人口最多的年份 ##

### 1.题目描述 ###

> 给你一个二维整数数组 `logs` ，其中每个 `logs[i] = [birthi, deathi]` 表示第 `i` 个人的出生和死亡年份。
> 
> 年份 `x` 的 **人口** 定义为这一年期间活着的人的数目。第 `i` 个人被计入年份 `x` 的人口需要满足：`x` 在闭区间 `[birthi, deathi - 1]` 内。注意，人不应当计入他们死亡当年的人口中。
> 
> > 返回 **人口最多** 且 **最早** 的年份。
> 
> **提示：**
> 
>  *  `1 <= logs.length <= 100`
>  *  `1950 <= birthi < deathi <= 2050`

力扣:[力扣][Link 1]

### 2.问题分析 ###

这一题是一道典型的差分数组的题目,但是这一题的差分很难察觉出来,因为它的差分数组的构建是隐性的.我们如果暴力求解的话,应该构建一个年份和人数相对应的数组.题目中明确说出生年份和死亡年份在1950到2050之间,因此我们可以构建一个长度为101长度的数组,然后每个人在出生到死亡之间的年份人数+1.说到这里我们就可以发现这里的思路就和上一题很想了,我们只需要构建一个差分数组,将出生日期的人数加一,死亡年份的人数减一,就是我们的差分数组了,每一年的人数只需要从前到后进行相加即可求出.

### 3.代码实现 ###

public int maximumPopulation(int[][] logs) {
            int offset = 1950;
            int[] diff = new int[101];
            for (int[] log : logs) {
                diff[log[0] - offset]++;
                diff[log[1] - offset]--;
            }
            int sum = 0, maxYear = 0, maxPeople = 0;
            for (int i = 0; i < diff.length; ++i) {
                sum += diff[i];
                if (sum > maxPeople) {
                    maxPeople = sum;
                    maxYear = i + offset;
                }
            }
            return maxYear;
    
        }

[a_i]: https://latex.csdn.net/eq?a_%7Bi%7D
[Link 1]: https://leetcode.cn/problems/maximum-population-year/description/