This is the 14th 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 47th day 🎈!
🚀 Algorithm 🚀

🌲 Duplicate elements exist

Given an array of integers, determine whether there are duplicate elements.

The function returns true if there is a value that appears in the array at least twice. Return false if each element in the array is different

Example 1:

Input:1.2.3.1] output:true
Copy the code

Example 2:

Input:1.2.3.4] output:false
Copy the code

Example 3:

Input:1.1.1.3.3.4.3.2.4.2] output:true
Copy the code

🌻C# method: sort

After sorting the numbers from smallest to largest, the repeating elements of the array must appear in adjacent positions.

Thus, we can scan a sorted array and determine each time if two adjacent elements are equal, which indicates the presence of duplicate elements.

Thinking analytical

Code:

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
            Array.Sort(nums);
            bool flag = false;
            for (int i = 1; i < nums.Length; i++)
            {
                if (nums[i- 1]==nums[i])
                {
                    flag = true;
                    break; }}returnflag; }}Copy the code

The execution result

By execution time:124Ms, in all C# beat 19.54% of users in submissionMemory consumption:28.6MB, in all C# beat 76.05% of users in submission
Copy the code

Complexity analysis

Time complexity: O(nlogn) Space complexity: O(logn)Copy the code

🌻Java Method 1: Sort

After sorting the numbers from smallest to largest, the repeating elements of the array must appear in adjacent positions.

Thus, we can scan a sorted array and determine each time if two adjacent elements are equal, which indicates the presence of duplicate elements.

Code:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true; }}return false; }}Copy the code

The execution result

By execution time:3Ms, beat out all Java commits99.56% user memory consumption:41.7MB, beat out all Java commits75.14% of the userCopy the code

Complexity analysis

Time complexity: O(nlog n) Space complexity: O(logN)Copy the code

🌻Java Method 2: Hash table

For each element in the array, we insert it into the hash table.

If an element is inserted and found to already exist in the hash table, a duplicate element exists.

Code:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if(! set.add(x)) {return true; }}return false; }}Copy the code

The execution result

By execution time:5Ms, beat out all Java commits57.66% user memory consumption:42.4MB, beat out all Java commits51.49% of the userCopy the code

Complexity analysis

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

💬 summary

  • Today is the forty-seventh day of the buckle algorithm clocking!
  • 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!

🚀 past quality articles to share

  • ❤ ️ Unity based to zero entry | the Unity game engine from 0 to 1 system study route suggest collection 】 【 comprehensive summary -!
  • 🧡 Spend a day making a high quality aircraft war game with over 10,000 word Unity complete tutorial! Beautiful school sister saw the call 666!
  • 💛 recall childhood and small partners played together the classic game [bomb people small game] production process + analysis
  • 💚 overnight a night to make a similar CS first person shooting game Demo! Turns out making games isn’t so hard
  • 🤍 blast liver a whole weekend to write a similar royal war real-time combat game Demo! More than 20,000 words game production process + analysis!
  • 💙 a similar “dinosaur kombat” horizontal version of the arcade fighting game how to make? | to learn together The way the source code suggest collect learning 】 【 code text is not easy,
  • 💜 super practical skills | 】 to improve writing quality and speed will learn skills: Typora figure bed configuration details