Easy

题目描述

给定一个整数数组 nums，其中 nums[i] 要么是正整数，要么是 -1。我们需要为每个 -1 找到对应的正整数，称为最后访问的整数。

为了实现这个目标，让我们定义两个空数组：seen 和 ans。

从数组 nums 的开头开始迭代：

  • 如果遇到正整数，将其添加到 seen 的前面。
  • 如果遇到 -1，设 k 为到目前为止连续看到的 -1 的数量（包括当前的 -1）：
    • 如果 k 小于或等于 seen 的长度，将 seen 的第 k 个元素添加到 ans。
    • 如果 k 严格大于 seen 的长度，将 -1 添加到 ans。

返回数组 ans。

示例 1：

输入：nums = [1,2,-1,-1,-1]
输出：[2,1,-1]

示例 2：

输入：nums = [1,-1,2,-1,-1]
输出：[1,2,1]

约束条件：

  • 1 <= nums.length <= 100
  • nums[i] == -1 或 1 <= nums[i] <= 100

解题思路

这道题要求我们按照题目描述的规则进行模拟。核心思路如下：

算法步骤：

  1. 维护一个 seen 数组存储遇到的正整数（按遇到的逆序存储）
  2. 维护一个计数器 k 记录连续遇到的 -1 的个数
  3. 遍历输入数组：
    • 遇到正整数时：重置 k = 0，将该数插入到 seen 的开头
    • 遇到 -1 时：k++，如果 k <= seen.size()，将 seen[k-1] 添加到结果；否则添加 -1

关键点：

  • seen 数组需要支持在前端插入元素，可以使用 deque 或者 vector 配合 insert 操作
  • 连续的 -1 会让 k 递增，非连续时 k 重置为 0
  • 题目要求的是第 k 个元素，对应数组索引是 k-1

时间复杂度： 每个元素最多被处理一次，插入操作在最坏情况下是 O(n)，总体 O(n²)
空间复杂度： O(n) 用于存储 seen 数组和结果数组

代码实现

class Solution {
public:
    vector<int> lastVisitedIntegers(vector<int>& nums) {
        vector<int> seen;
        vector<int> ans;
        int k = 0;
        
        for (int num : nums) {
            if (num > 0) {
                k = 0;
                seen.insert(seen.begin(), num);
            } else {
                k++;
                if (k <= seen.size()) {
                    ans.push_back(seen[k-1]);
                } else {
                    ans.push_back(-1);
                }
            }
        }
        
        return ans;
    }
};

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        ans = []
        k = 0
        
        for num in nums:
            if num > 0:
                k = 0
                seen.insert(0, num)
            else:
                k += 1
                if k <= len(seen):
                    ans.append(seen[k-1])
                else:
                    ans.append(-1)
        
        return ans

public class Solution {
    public IList<int> LastVisitedIntegers(int[] nums) {
        List<int> seen = new List<int>();
        List<int> ans = new List<int>();
        int k = 0;
        
        foreach (int num in nums) {
            if (num > 0) {
                k = 0;
                seen.Insert(0, num);
            } else {
                k++;
                if (k <= seen.Count) {
                    ans.Add(seen[k-1]);
                } else {
                    ans.Add(-1);
                }
            }
        }
        
        return ans;
    }
}

var lastVisitedIntegers = function(nums) {
    let seen = [];
    let ans = [];
    let k = 0;
    
    for (let num of nums) {
        if (num > 0) {
            k = 0;
            seen.unshift(num);
        } else {
            k++;
            if (k <= seen.length) {
                ans.push(seen[k-1]);
            } else {
                ans.push(-1);
            }
        }
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)遍历数组 O(n)，每次插入操作最坏 O(n)
空间复杂度O(n)seen 数组和结果数组的存储空间