IOS 算法(基础篇) ----- 人口最多的年份

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

例子:

输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。

输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释： 人口最多为 2 ，分别出现在 1960 和 1970 , 其中最早年份是 1960 。

解题思路:

1.遍历法

这种比较好理解, 由于年份数量比较少, 那么我们维护一个年份对应数组 1950, 1951 .... 2050 → [0, 0 ... 0]

遍历logs, 在对应的 [birthi, deathi] 区间中, 依次累加, 最后取年份人数最多最小元素

例: logs = [[1950,1961],[1960,1971],[1970,1981]]

设置数组 temp = [0, 0, 0 ... 0], 其中temp[0]为1950人数, temp[1]为1951人数, ... temp[99]为2050人数

遍历log

[1950,1961]: 再遍历[1950,1961], 找到对应temp下标, 依次+1 (即 1950 ~ 1961即下标0~10元素+1)
[1960,1971]: 再遍历[1960,1971], 找到对应temp下标, 依次+1 (即 1960 ~ 1971即下标10~20元素+1)
[1970,1981]: 再遍历[1970,1981], 找到对应temp下标, 依次+1 (即 1970 ~ 1981即下标20~30元素+1)
这种方法只适合数据量比较少的情况

代码

    func maximumPopulation(_ logs: [[Int]]) -> Int {

        var temp = Array(repeating: 0, count: 100),  tempYears = 0, tempSum = 0
        
        for i in logs {
            
            for j in i[0]..<i[1] {
                
                temp[j - 1950] += 1
                if (temp[j - 1950] > tempSum) || (temp[j - 1950] == tempSum && j < tempYears) {
                
                    tempYears = j
                    tempSum = temp[j - 1950]
                
                }
            }
        }
         
        return tempYears;

    }

2.差分法

维护一个差分数组temp, 循环log数组, 通过首位 +1, 末尾 -1(人出生年份对应的变化量加上1, 同时将死亡年份对应的变化量减去1, 中间不用处理), 进行处理。 之后循环差分数组依次相加, 记找到最大的和数组下标 + 1950 就是对于随求年份

例: [[1950,1961],[1960,1971],[1970,1981]], 初始差分数组temp = [0, 0, .... 0], 初始最小年份 year = 1950

循环logs结果: temp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

循环temp 每一项累加, 和多于之前和 (其实就是最大人数), 替换最大和, 年份替换成当前数组下标, 最后返回 year + 1950 即可

代码

    func maximumPopulation(_ logs: [[Int]]) -> Int {

        var temp = Array(repeating:0 ,count: 101)
        
        for log in logs {
            temp[log[0] - 1950] += 1
            temp[log[1] - 1950] -= 1
        }
        
        var sum = 0, max = 0, year = 1950
        
        for i in 0..<101 {
            sum += temp[i]
            if sum > max {
                max = sum
                year = i
            }
        }

        return year + 1950

    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址