如何在O(n)复杂度下为List前置元素填充后续非空company属性

问题背景 #

现有如下Person类：

class Person {
    String name;
    String company;

    // 构造方法
    Person(String name, String company) {
        this.name = name;
        this.company = company;
    }
}

输入为不可变列表：

List<Person> persons = List.of(
        new Person("Bill", null),
        new Person("Andrew", null),
        new Person("Chris", "Magic"),
        new Person("Max", null),
        new Person("Garry", null),
        new Person("Mark", "Risky")
);

需求：通过一次遍历完成处理，用后续元素的非空company值填充前置元素的null值，最终得到如下结果，要求严格O(n)时间复杂度，禁止排序、反转等操作。

预期结果：

List<Person> resultPersons = List.of(
        new Person("Bill", "Magic"),
        new Person("Andrew", "Magic"),
        new Person("Chris", "Magic"),
        new Person("Max", "Risky"),
        new Person("Garry", "Risky"),
        new Person("Mark", "Risky")
);

当前实现不符合要求（包含排序和反转，时间复杂度高于O(n)）：

// key - person id, value - company
NavigableMap<Integer, String> companyDict = new TreeMap<>();

List<PersonCard> result = persons.stream()
      .sorted(PERSON_COMPARATOR)
      .peek(p -> fillCompanyName(p, companyDict)) // fill map with personId and company
      .map(p -> createPersonCard(p, companyDict)) // use map with companies to get company by person id for creating another object
      .collect(Collectors.toList());

Collections.reverse(result);

解决方案 #

核心思路：从列表尾部向前遍历，维护一个变量记录当前遇到的最近非空company值，每遍历到一个元素，就将该值赋值给当前元素的company（若原company为null）；若当前元素company非空，则更新记录的最近值。

由于输入列表是List.of()创建的不可变列表，无法直接修改原对象，因此需要创建新的Person对象存入结果列表。

代码实现 #

// 初始化结果列表，指定容量提升百万级数据处理效率
List<Person> result = new ArrayList<>(persons.size());
// 先填充占位符，后续替换
for (int i = 0; i < persons.size(); i++) {
    result.add(null);
}

String currentCompany = null;
// 从后往前遍历输入列表
for (int i = persons.size() - 1; i >= 0; i--) {
    Person original = persons.get(i);
    // 若当前元素company非空，更新记录的最近公司值
    if (original.company != null) {
        currentCompany = original.company;
    }
    // 创建新对象存入结果列表对应位置
    result.set(i, new Person(original.name, currentCompany));
}

// result即为符合要求的结果列表

复杂度说明 #

• 时间复杂度：O(n)，仅进行一次从后到前的遍历，所有操作均为常数时间。
• 空间复杂度：O(n)，用于存储结果列表（若输入为可变列表且允许修改原对象，可做到O(1)额外空间）。

该实现完全满足O(n)性能要求，无排序、反转等耗时操作，适配百万级别的数据量处理。

内容的提问来源于stack exchange，提问作者lenriq