Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.
Example 1:
Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
Example 2:
Input: arr = [1,2,3,4], k = 2 Output: 6 Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
Constraints:
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j] for 1 <= i < j <= arr.lengthFollow up:
Could you solve this problem in less than O(n) complexity?
program main
implicit none
integer, parameter :: n = 10
integer, dimension(n) :: arr
integer :: k
integer :: result
! Example 1
arr = [2, 3, 4, 7, 11]
k = 5
result = findKthMissingPositiveInteger(arr, k)
print '(A, I0)', 'Example 1: ', result
! Example 2
arr = [1, 2, 3, 4]
k = 2
result = findKthMissingPositiveInteger(arr, k)
print '(A, I0)', 'Example 2: ', result
contains
function findKthMissingPositiveInteger(arr, k) result(result_)
implicit none
integer, intent(in) :: arr(:), k
integer :: result_
integer :: i, j
result_ = -1
do i = 1, size(arr) - 1
if (arr(i) + 1 /= arr(i+1)) then
exit
end if
end do
if (i == size(arr)) then
result_ = arr(size(arr)) + k
else
do j = i + 1, size(arr) - 1
if (arr(j) > arr(i) + k) then
result_ = arr(i) + k
exit
end if
end do
end if
end function findKthMissingPositiveInteger
end program maintemp.f95:10:4:
10 | arr = [2, 3, 4, 7, 11]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (10 and 5)
temp.f95:16:4:
16 | arr = [1, 2, 3, 4]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (10 and 4)
module missing_integer
implicit none
private
public :: find_missing_integer
contains
function find_missing_integer(arr, k) result(missing_integer)
implicit none
integer, intent(in) :: arr(:), k
integer :: missing_integer
integer :: i, j
missing_integer = -1
! Iterate through the array and find the first missing integer
do i = 1, size(arr) - 1
if (arr(i) + 1 /= arr(i + 1)) then
missing_integer = arr(i) + 1
exit
end if
end do
! If the first missing integer is not found, then the last element of the array is missing
if (missing_integer == -1) then
missing_integer = arr(size(arr)) + 1
end if
! If the kth missing integer is not found, then the kth missing integer is the last missing integer
if (missing_integer == -1) then
missing_integer = arr(size(arr)) + 1
end if
! If the kth missing integer is found, then return it
if (missing_integer /= -1) then
return
end if
! If the kth missing integer is not found, then iterate through the array and find the kth missing integer
do i = 1, size(arr) - 1
if (arr(i) + 1 /= arr(i + 1)) then
j = i + 1
do while (j <= size(arr) - 1)
if (arr(j) + 1 /= arr(j + 1)) then
if (k == 1) then
missing_integer = arr(j) + 1
exit
else
k = k - 1
end if
end if
j = j + 1
end do
if (missing_integer /= -1) then
return
end if
end if
end do
end function find_missing_integer
end module missing_integer
program test_missing_integer
use missing_integer
implicit none
integer, parameter :: arr1(5) = [2, 3, 4, 7, 11]
integer, parameter :: arr2(4) = [1, 2, 3, 4]
integer, parameter :: k1 = 5
integer, parameter :: k2 = 2
integer :: missing_integer
missing_integer = find_missing_integer(arr1, k1)
write (*, *) "Missing integer for arr1 and k1:", missing_integer
missing_integer = find_missing_integer(arr2, k2)
write (*, *) "Missing integer for arr2 and k2:", missing_integer
end program test_missing_integer
temp.f95:47:28:
47 | k = k - 1
| 1
Error: Dummy argument ‘k’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:61:9:
61 | use missing_integer
| 1
Fatal Error: Cannot open module file ‘missing_integer.mod’ for reading at (1): No such file or directory
compilation terminated.
def find_diagonal_order(nums):
diagonals = {}
for i in range(len(nums)):
for j in range(len(nums[i])):
if i + j not in diagonals:
diagonals[i + j] = []
diagonals[i + j].append(nums[i][j])
res = []
for key in diagonals:
res.extend(reversed(diagonals[key]))
return res
First, we iterate through the 2D array nums using nested loops over i and j. At each loop iteration, we insert the current element nums[i][j] into diagonals[i + j] list for a specific diagonal associated with (i + j). If the list doesn't exist, we create it.
Then, we iterate through the diagonals and reverse the order of each diagonal list because elements with larger row index should come first in the result. We use std::reverse() in C++, Collections.reverse() in Java, reversed() in Python, and Array.prototype.reverse() in JavaScript.
Finally, we concatenate the reversed diagonal lists to form the result array using std::vector::insert() in C++, List.addAll() in Java, list.extend() in Python, and by using the spread operator (...) in JavaScript.
#include <vector>
std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& nums) {
std::vector<int> res;
int m = nums.size();
std::map<int, std::vector<int>> diagonals;
for (int i = 0; i < m; i++) {
for (int j = 0; j < nums[i].size(); j++) {
diagonals[i + j].push_back(nums[i][j]);
}
}
for (auto& diag : diagonals) {
std::reverse(diag.second.begin(), diag.second.end());
res.insert(res.end(), diag.second.begin(), diag.second.end());
}
return res;
}
First, we iterate through the 2D array nums using nested loops over i and j. At each loop iteration, we insert the current element nums[i][j] into diagonals[i + j] list for a specific diagonal associated with (i + j). If the list doesn't exist, we create it.
Then, we iterate through the diagonals and reverse the order of each diagonal list because elements with larger row index should come first in the result. We use std::reverse() in C++, Collections.reverse() in Java, reversed() in Python, and Array.prototype.reverse() in JavaScript.
Finally, we concatenate the reversed diagonal lists to form the result array using std::vector::insert() in C++, List.addAll() in Java, list.extend() in Python, and by using the spread operator (...) in JavaScript.