496. Next Greater Element I

LeetCode easy оригинал: C# #array #csharp #easy #hash-table #leetcode #search
LeetCode Static

Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.

Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.

Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.

Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

Explanation: The next greater element for each value of nums1 is as follows:

- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.

- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

C# решение

сопоставлено/оригинал 
public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.Length];
        Array.Fill(res, -1);
        
        for (int i = 0; i < nums1.Length; i++) {
            bool found = false;
            for (int j = 0; j < nums2.Length; j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
}

C++ решение

auto-draft, проверить перед отправкой 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& NextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>& res = new int[nums1.size()];
        Array.Fill(res, -1);
        
        for (int i = 0; i < nums1.size(); i++) {
            bool found = false;
            for (int j = 0; j < nums2.size(); j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
}

Java решение

сопоставлено/оригинал 
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        int j;
    
        for (int i = 0; i < nums1.length; i++) {
            boolean found = false;
            for (j = 0; j < nums2.length; j++) {
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
    
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
            }
            if (j == nums2.length) {
                res[i] = -1;
            }
        }
    
        return res;
    }
}

JavaScript решение

сопоставлено/оригинал 
class Solution {
    nextGreaterElement(nums1, nums2) {
        let res = Array(nums1.length).fill(-1);
        
        for (let i = 0; i < nums1.length; i++) {
            let found = false;
            for (let j = 0; j < nums2.length; j++) {
                if (nums2[j] === nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
}

Python решение

сопоставлено/оригинал 
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums1)
        
        for i in range(len(nums1)):
            found = False
            for j in range(len(nums2)):
                if nums2[j] == nums1[i]:
                    found = True
                if found and nums2[j] > nums1[i]:
                    res[i] = nums2[j]
                    break
        
        return res

Go решение

сопоставлено/оригинал 
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i := range res {
        res[i] = -1
    }
    
    for i := 0; i < len(nums1); i++ {
        found := false
        for j := 0; j < len(nums2); j++ {
            if nums2[j] == nums1[i] {
                found = true
            }
            if found && nums2[j] > nums1[i] {
                res[i] = nums2[j]
                break
            }
        }
    }
    
    return res
}

Algorithm

Инициализация и поиск совпадений

Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.

Поиск следующего большего элемента

После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.

Заполнение результата

Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.