ค้นหาหมายเลขซ้ำแรกในอาร์เรย์ที่กำหนด

คำชี้แจงปัญหา

สามารถมีตัวเลขที่ซ้ำกันได้หลายหมายเลขในไฟล์ แถว แต่คุณต้องหาตัวเลขที่เกิดซ้ำครั้งแรกในอาร์เรย์ที่กำหนด (เกิดขึ้นในครั้งที่สอง)

ตัวอย่าง

อินพุต

12

5 4 2 8 9 7 12 5 6 12 4 7

เอาท์พุต

5 เป็นองค์ประกอบแรกที่เกิดซ้ำ

แนวทางที่ 1 เพื่อค้นหาหมายเลขที่ซ้ำกันแรก

เพียงแค่เราสามารถใช้ Hashing โดยที่เราแฮชค่าองค์ประกอบของอาร์เรย์และเพิ่มจำนวนครั้งที่เกิดขึ้น ทันทีที่เราได้องค์ประกอบที่มีการนับ 1 เช่นซึ่งเกิดขึ้นแล้วเราจะได้รับองค์ประกอบที่ซ้ำกันครั้งแรก

ขั้นตอนวิธี

1. สำรวจแต่ละองค์ประกอบของอาร์เรย์

2. เพิ่มความถี่ของแต่ละองค์ประกอบ

3. หากองค์ประกอบใด ๆ ที่มีความถี่มากกว่า 1 ให้พิมพ์ตัวเลขนั้นโดยตรง

การดำเนินงาน

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  unordered_map<int,int> m;
  int ans=0;
  for(int i=0;i<n;i++)
  {
      m[a[i]]++;
      if(m[a[i]]>1)
      {
          ans=a[i];
          break;
      }
  }
  if(ans==0)
  {
      cout<<"No element repeated"<<endl;
  }
  else
  {
    cout<<ans<<endl;
  }
}

โปรแกรม Java

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap <Integer,Integer> m = new HashMap<Integer, Integer>();
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int x = m.get(a[i])==null ? 1: m.get(a[i])+1;
            m.put(a[i], x);
            if(m.get(a[i])>1)
            {
                ans=a[i];
                break;
            }
        }
        if(ans==0)
        {
            System.out.println("No element repeated");
        }
        else
        {
          System.out.println(ans);
        }
    }
}

12
5 4 2 8 9 7 12 5 6 12 4 7

5

การวิเคราะห์ความซับซ้อนเพื่อค้นหาหมายเลขที่ซ้ำกันแรก

ความซับซ้อนของเวลา - O (N) โดยที่ N คือขนาดของอาร์เรย์ ที่นี่เราทำซ้ำบนอาร์เรย์และจัดเก็บความถี่ / จำนวนองค์ประกอบในแผนที่แฮช

ความซับซ้อนของอวกาศ - O (N) เนื่องจากเรานับองค์ประกอบความถี่ o และขนาดสูงสุดที่เป็นไปได้ของแผนที่แฮชคือ O (n)

แนวทางที่ 2 เพื่อค้นหาหมายเลขที่ซ้ำกันแรก

ที่นี่เราใช้แผนที่ที่เก็บองค์ประกอบนั้นที่มีอยู่ในอาร์เรย์หรือไม่ หากองค์ประกอบมีอยู่แสดงว่ามี จริง เกี่ยวกับองค์ประกอบนั้นในแผนที่ หากองค์ประกอบไม่มีอยู่แสดงว่าองค์ประกอบนั้นคงอยู่ เท็จ เกี่ยวกับองค์ประกอบนั้นในแผนที่

ขั้นตอนวิธี

1. ใช้แผนที่โดยสร้างค่าขององค์ประกอบอาร์เรย์เป็นคีย์และนับเป็นคู่คีย์ - ค่า

2. เริ่มต้นคู่โดยนับเป็น 1 และเพิ่มขึ้น

3. ทันทีที่เราได้องค์ประกอบที่มีจำนวนเท่ากับ 1 เราจะได้รับองค์ประกอบที่เกิดซ้ำครั้งแรก

การดำเนินงาน

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  map <int,bool> M; // create a map with key as the array element and value as if it is present or not
  map <int,bool> :: iterator it;
  for(int i=0;i<n;i++)
    {
      it = M.find(arr[i]); //find the array element in map
      if(it != M.end()) // if present then it is the first element to be repeated
        {
          cout<<arr[i] <<endl;
          return 0;
        }
      else
        M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
    }
  cout<<"No element repeated"<<endl;
  return 0;
  
}

โปรแกรม Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Map <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
        int frank=0;
        for(int i=0;i<n;i++)
        {
            boolean temp = m.containsValue(a[i]);
            if(temp) // if present then it is the first element to be repeated
            {
                System.out.println(a[i]);
                frank=1;
                i=n;
            }
            else
            {
               m.put(a[i],1); //else insert it into the map setting the value as true
            }
          }
        if(frank==0)
        System.out.println("No element repeated");
    }
}

6
1 2 3 4 5 6

No element repeated

การวิเคราะห์ความซับซ้อนเพื่อค้นหาหมายเลขที่ซ้ำกันแรก

คำถามสัมภาษณ์ยอดนิยม