This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 61 days of continuous clocking of force button algorithm 🎈!
🚀 Algorithm 🚀

🌲 The next larger element I

You are given two arrays with no duplicate elements, nums1 and nums2, where nums1 is a subset of nums2.

Find the next value greater in nums2 for each element in nums1.

The next larger element of the number x in nums1 is the first larger element of x to the right of the corresponding position in nums2. If no, -1 is displayed at the corresponding position.

Example:

Enter: nums1 = [4.1.2], nums2 = [1.3.4.2]. Output: [- 1.3.- 1For numbers in num14, you can't find the next larger number in the second array, so output- 1. For numbers in num11, the number in the second array1The next large number on the right is3. For numbers in num12, there is no next larger number in the second array, so output- 1 。

Copy the code

Example 2:

Enter: nums1 = [2.4], nums2 = [1.2.3.4]. Output: [3.- 1For numbers in num12The next large number in the second array is3. For numbers in num14, there is no next larger number in the second array, so output- 1 。
Copy the code

Tip:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are different
  • All integers in nums1 also appear in nums2

🌻C# method: violent solution

The easy brute force solution is to traverse the elements in NUMs1 and find out if there is a next maximum in nums2.

Code:

public class Solution {
public int[] NextGreaterElement(int[] nums1, int[] nums2)
        {
            var result = new int[nums1.Length];

            for (int i = 0; i < nums1.Length; i++)
            {
                // Initialize the corresponding result to -1
                result[i] = - 1;
                // whether the target value in nums1 is found in nums2
                bool IsTargetFinded = false;
                for (int j = 0; j < nums2.Length; j++)
                {
                    if (nums2[j] > nums1[i] && IsTargetFinded == true)
                    {
                        result[i] = nums2[j];
                        // The first result is returned
                        break;
                    }
                    else if (nums2[j] == nums1[i])
                    {
                        IsTargetFinded = true; }}}returnresult; }}Copy the code

The execution result

By execution time:136Ms, in all CBeat 94.38% users in # commitMemory consumption:40.2MB, in all C# beat 14.61% of users in submission
Copy the code

🌻Java method: Brute force solution

There are no duplicate elements in each array.

For each element in nums1[I], find it in nums2, and traverse right to find the first element greater than nums1[I].

Code:

import java.util.Arrays;

public class Solution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        int[] res = new int[len1];
        if (len1 < 1) {
            return res;
        }

        for (int i = 0; i < len1; i++) {
            int curVal = nums1[i];
            int j = 0;
            while(j < len2 && nums2[j] ! = curVal) { j++; }Nums [j] = nums[I]
            j++;
            while (j < len2 && nums2[j] < curVal) {
                j++;
            }

            if (j == len2) {
                res[i] = -1;
                continue;
            }
            res[i] = nums2[j];
        }
        returnres; }}Copy the code

The execution result

By execution time:7Ms, beat out all Java commits15.01% user memory consumption:38.7MB, beat out all Java commits28.64% of the userCopy the code

Complexity analysis

Time complexity: O(nm) Space complexity: O(nm)Copy the code

💬 summary

  • Today is the sixty-sixth day of the buckle algorithm.
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!