2899. Last Visited Integers
Description
Given an integer array nums
where nums[i]
is either a positive integer or -1
. We need to find for each -1
the respective positive integer, which we call the last visited integer.
To achieve this goal, let's define two empty arrays: seen
and ans
.
Start iterating from the beginning of the array nums
.
- If a positive integer is encountered, prepend it to the front of
seen
. - If
-1
is encountered, letk
be the number of consecutive-1
s seen so far (including the current-1
),- If
k
is less than or equal to the length ofseen
, append thek
-th element ofseen
toans
. - If
k
is strictly greater than the length ofseen
, append-1
toans
.
- If
Return the array ans
.
Example 1:
Input: nums = [1,2,-1,-1,-1]
Output: [2,1,-1]
Explanation:
Start with seen = []
and ans = []
.
- Process
nums[0]
: The first element in nums is1
. We prepend it to the front ofseen
. Now,seen == [1]
. - Process
nums[1]
: The next element is2
. We prepend it to the front ofseen
. Now,seen == [2, 1]
. - Process
nums[2]
: The next element is-1
. This is the first occurrence of-1
, sok == 1
. We look for the first element in seen. We append2
toans
. Now,ans == [2]
. - Process
nums[3]
: Another-1
. This is the second consecutive-1
, sok == 2
. The second element inseen
is1
, so we append1
toans
. Now,ans == [2, 1]
. - Process
nums[4]
: Another-1
, the third in a row, makingk = 3
. However,seen
only has two elements ([2, 1]
). Sincek
is greater than the number of elements inseen
, we append-1
toans
. Finally,ans == [2, 1, -1]
.
Example 2:
Input: nums = [1,-1,2,-1,-1]
Output: [1,2,1]
Explanation:
Start with seen = []
and ans = []
.
- Process
nums[0]
: The first element in nums is1
. We prepend it to the front ofseen
. Now,seen == [1]
. - Process
nums[1]
: The next element is-1
. This is the first occurrence of-1
, sok == 1
. We look for the first element inseen
, which is1
. Append1
toans
. Now,ans == [1]
. - Process
nums[2]
: The next element is2
. Prepend this to the front ofseen
. Now,seen == [2, 1]
. - Process
nums[3]
: The next element is-1
. This-1
is not consecutive to the first-1
since2
was in between. Thus,k
resets to1
. The first element inseen
is2
, so append2
toans
. Now,ans == [1, 2]
. - Process
nums[4]
: Another-1
. This is consecutive to the previous-1
, sok == 2
. The second element inseen
is1
, append1
toans
. Finally,ans == [1, 2, 1]
.
Constraints:
1 <= nums.length <= 100
nums[i] == -1
or1 <= nums[i] <= 100
Solutions
Solution 1: Simulation
We can directly simulate according to the problem statement. In the implementation, we use an array $nums$ to store the traversed integers, and an integer $k$ to record the current number of consecutive $prev$ strings. If the current string is $prev$, we take out the $|nums| - k-th$ integer from $nums$. If it does not exist, we return $-1$.
The time complexity is $O(n)$, where $n$ is the length of the array $words$. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|