📢 preface

🚀 Algorithm problem 🚀

• 🌲 Punching out an algorithm problem every day is not only a learning process, but also a sharing process 😜
• 🌲 Tip: the problem-solving programming languages in this column are C# and Java
• 🌲 To maintain a state of learning every day, let's work together to become the great God of algorithm 🧐!
• 🌲 Today is the 48th day of punching out the force deduction algorithm 🎈!

🚀 Algorithm problem 🚀

🌲 Example of original question: duplicate Element II exists

Given an integer array and an integer k, judge whether there are two different indexes I and j in the array, so that num [i] = num [J], and the absolute value of the difference between I and j is at most K.

Example 1:

input: nums = [1,2,3,1], k = 3
 output: true

Example 2:

input: nums = [1,0,1,1], k = 1
 output: true

Example 3:

input: nums = [1,2,3,1,2,3], k = 2
 output: false

🌻 C# method: traversal

Traverse the array to judge whether the element exists in the Hash table. If it does not exist, insert and save the current array subscript. If it exists, judge the difference between the last insertion and the current subscript. If it is less than k, it indicates that the meaning of the question is met

code:

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        bool flag = false;
        for(int i = 0; i < nums.Length; i++)
        {
            if (dic.ContainsKey(nums[i]))
            {
                if (i-dic[nums[i]]<= k)
                {
                    return true;
                }
                dic[nums[i]]=i;
            }
            else
            {
                dic[nums[i]] = i;
            }
        }
        return flag;
    }
}

results of enforcement

adopt
 Execution time: 272 ms，At all C# Defeated 46.32% of users in submission
 Memory consumption: 50 MB，At all C# Beat 50.00% of users in submission

Complexity analysis

Time complexity: O( n ),among n Is the number of nodes in the tree
 Space complexity: O( H )，among H Is the height of the tree

🌻 Java method 1: linear search

Train of thought analysis

Compare each element with the kk elements before it to see if they are equal.

This algorithm maintains a kk size sliding window, and then searches this window for the existence of elements equal to the current element.

code:

class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}
// Time Limit Exceeded.
}

results of enforcement

adopt
 Execution time: 151 ms，At all Java  Defeated 14 in submission.74%User
 Memory consumption: 50.3 MB，At all Java Defeated 47 in submission.20%User

🌻 Java method 2: hash table

Train of thought analysis
Maintain this kk size sliding window with a hash table.

In the previous method, we know that the search operation with logarithmic time complexity is not enough. In this method, we need a data structure that supports search, delete and insert operations in constant time, that is, hash table. The implementation of this algorithm is almost the same as method 2.

Traverse the array and do the following for each element:

• Search the hash table for the current element, and return true if found.
• Inserts the current element into the hash table.
• If the size of the current hash table exceeds kk, delete the oldest element in the hash table.

Returns false.

code:

class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}
}

results of enforcement

adopt
 Execution time: 29 ms，At all Java  Defeated 21 in submission.67%User
 Memory consumption: 53 MB，At all Java Defeated 25 in submission.08%User

💬 summary

• Today is the 48th day of punching out the force deduction algorithm!
• This paper uses C# and Java programming languages to solve problems
• Some methods are also written by Likou God, and they are also shared while learning. Thanks again to the algorithm bosses
• That's the end of today's algorithm sharing. See you tomorrow!
  

🚀 Previous high-quality article sharing

• ❤️Unity zero foundation to entry | systematic learning route of game engine unity from 0 to 1 [comprehensive summary - suggestions collection]!
• 🧡Spend a day doing a high-quality aircraft war game and have a complete tutorial of 10000 words Unity! Beautiful Xuemei looked and called 666!
• 💛Recall the production process + analysis of the classic game [Bomber game] played with my friends in childhood
• 💚A first person shooting game Demo similar to CS made all night! It's not difficult to play games
• 🤍Explosive liver wrote a real-time combat game Demo similar to the Royal war all weekend! More than 20000 word game production process + analysis!
• 💙How to make a horizontal arcade fighting game similar to "dinosaur quick fight"| Learn together and send the source code by the way [code text is not easy, it is recommended to collect and learn]
• 💜[super practical skills] | necessary skills to improve the quality and speed of writing: detailed description of Typora drawing bed configuration