差分数组

leetcode - 5750. 人口最多的年份

题目描述:

  • 给你一个二维整数数组 logs ,其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

  • 年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足:x 在闭区间 [birthi, deathi - 1] 内。注意,人不应当计入他们死亡当年的人口中。

  • 返回 人口最多 且 最早 的年份。

这是今天leetcode第240场周赛的easy题,早上周赛写的时候用暴力解的。

思路如下:
先用map存放每年的健在的人数,然后根据map的value降序排序,若value相等再根据key升序排序。(当然,也可以直接用数组存,那样更简单)。

以下为比赛时写的代码:

public int maximumPopulation(int[][] logs) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < logs.length; i++) { // 统计每个年份活着人数
			int birth = logs[i][0];
			int death = logs[i][1];
			for (int j = birth; j < death; j++) {
				if (!map.containsKey(j)) {
					map.put(j, 1);
				} else {
					map.put(j, map.get(j) + 1);
				}
			}
		}
		// 对map按照value降序排序
		List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet()); // 将map.entrySet()转化为list
		Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
			@Override
			public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
				// (1)对map按照value降序排序
				if (o2.getValue() != o1.getValue()) {
					return o2.getValue() - o1.getValue();
				}
				// (2)再按年份升序排序
				return o1.getKey() - o2.getKey();
			}
		});
		
		return list.get(0).getKey();
    }

由于这题数据比较弱,早上周赛这样写是过了的。但是,一旦数据给的很多,并且 [birth, death) 区间跨度很大,这样频繁对数组中进行区间修改操作的话,很大可能是会 TLE 的

后来周赛完了后,看了吴自华dalao发的题解,意识到可以用差分数组求解本题更优。

差分数组推荐看这篇博客:什么是差分数组?

差分数组的优点:

  • 差分数组(记作 minus)定义如下:
    1. minus[0] = arr[0];
    2. minus[i] = arr[i] - arr[i - 1]; (i > 0)
  • 利用差分数组方便进行对数组进行区间修改操作。
  • 当要对数组arr中 [left, right] 中元素统一加(或减)d时,不用再从 left 遍历 到 right ,然后分别对 [left, right]中每个元素分别加(或减)d,只需要修改差分数组minus即可。
  • 当要对数组arr中 [left, right] 中元素统一加(或减)d时,只需要修改差分数组:
    1. minus[left] += d;
    2. minus[right + 1] -= d; // 左闭右闭区间

吴自华dalao给出的差分数组解法如下:

public int maximumPopulation(int[][] logs) {
		int[] minus = new int[100]; // 差分数组:minus[i]=arr[i] -arr[i-1]
									// minus[0] = arr[0]
		for (int i = 0; i < logs.length; i++) {
			minus[logs[i][0] - 1950]++;
			minus[logs[i][1] - 1950]--; // 左闭右开区间 [birth, death),不用 + 1
		}
		int index = 0;
		for (int i = 1; i < minus.length; i++) {
			// 根据差分数组 minus 求原数组 arr的值,只不过这里不重新创建arr,仍用minus表示
			minus[i] += minus[i - 1];
			if (minus[i] > minus[index]) {
				index = i;
			}
		}

		return index + 1950;
	}

相似题目面试题 16.10. 生存人数

此题基本和 5750. 人口最多的年份 一模一样。

代码如下:

// 类似t5750
    public int maxAliveYear(int[] birth, int[] death) {
		int[] minus = new int[102]; // 差分数组:minus[i] = arr[i]-arr[i-1]
		for (int i = 0; i < birth.length; i++) {
			minus[birth[i] - 1900]++;
			minus[death[i] - 1900 + 1]--; // 左闭右闭区间 [birth[i], death[i]]
		}
		int index = 0;
		for (int i = 1; i < minus.length; i++) {
			minus[i] += minus[i - 1];
			if (minus[i] > minus[index]) {
				index = i;
			}
		}
		
		return index + 1900;
    }
上一篇:Linux下分文件编程


下一篇:【DB笔试面试64】在Oracle中,以下不属于集合操作符的是()