ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยค่าจำนวนเต็ม N งานของเราคือ สร้างโปรแกรมสำหรับค้นหาองค์ประกอบแรกที่ปรากฏในอาร์เรย์เป็นจำนวนคู่ . หากมีองค์ประกอบใดที่ตรงตามเงื่อนไขส่งคืน มิฉะนั้นให้คืนค่า -1 แสดงว่า เท็จ .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: arr[] = {2, 3, 7, 2, 3, 6, 4, 1, 2}
Output: 3 แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาคือการพิจารณาแต่ละองค์ประกอบของอาร์เรย์ทีละรายการ จากนั้นจึงตรวจสอบความถี่การเกิดขึ้นขององค์ประกอบแบบคู่ และส่งคืนองค์ประกอบแรกในอาร์เรย์ด้วยความถี่การเกิดขึ้นที่เท่ากัน อีกวิธีในการแก้ปัญหาคือการใช้ hash map โครงสร้างข้อมูล. สำหรับสิ่งนี้ เราจะสำรวจอาร์เรย์และสร้าง hash map ที่จัดเก็บองค์ประกอบพร้อมกับความถี่ของการเกิดเป็นสลับ กล่าวคือ จริงหรือเท็จ โดยพิจารณาจากข้อเท็จจริงที่ว่ามันเท่ากันหรือไม่ ซึ่งจะช่วยลดค่าใช้จ่ายในการตรวจสอบว่าความถี่ที่เกิดขึ้นเป็นจริงหรือเท็จ เนื่องจากปุ่มสลับจะแสดงผลลัพธ์ที่ต้องการ สำหรับแผนที่ องค์ประกอบแรกที่มีค่าเป็นจริง (แสดงถึงความถี่ของการเกิดขึ้น) คือผลลัพธ์ที่เราต้องการ
เราจะสำรวจอาร์เรย์และสำหรับแต่ละค่าในอาร์เรย์เช่น arr[i] เราจะตรวจสอบในแผนที่
หากไม่มีอยู่ในแผนที่ ให้เพิ่มลงในแผนที่ด้วยค่าสลับ 'เท็จ '. หากมีอยู่ในแผนที่ ให้สลับค่าปัจจุบันที่ตรงกับค่านั้น เช่น หากเป็น 'จริง ' ทำให้เป็น 'เท็จ ' และถ้าเป็น 'เท็จ ' ทำให้ 'จริง '.
หลังจากการวนซ้ำของอาร์เรย์ ให้วนซ้ำแผนที่และคืนค่าแรกด้วยค่าสลับที่สอดคล้องกันเป็น 'จริง '.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int findFirstEvenFreqVal(int arr[], int n){
unordered_map<int, bool> freqTogMap;
for (int i = 0; i < n; i++){
if (freqTogMap.find(arr[i]) == freqTogMap.end())
freqTogMap.insert(pair <int,bool> (arr[i],false));
else
{
bool val = freqTogMap.find(arr[i])->second;
if (val == true)
freqTogMap.find(arr[i])->second = false;
else
freqTogMap.find(arr[i])->second = true;
}
}
int j = 0;
for (j = 0; j < n; j++){
if (freqTogMap.find(arr[j])->second == true)
return arr[j];;
}
return -1;
}
int main(){
int arr[] = { 2, 4, 6, 8, 1, 6 };
cout<<"The first element of the array which appears even number of times is " <<findFirstEvenFreqVal(arr, 6);
return 0;
} ผลลัพธ์
The first element of the array which appears even number of times is 6
