ให้สตริง 's' ภารกิจคือการค้นหาอักขระที่ไม่ซ้ำกันตัวแรกซึ่งไม่ซ้ำกันในสตริงของอักขระที่กำหนดและส่งคืนดัชนีเป็นเอาต์พุต หากไม่มีอักขระดังกล่าวอยู่ในสตริงที่กำหนด เราจะคืนค่า '-1' เป็นเอาต์พุต ตัวอย่างเช่น
อินพุต-1 −
s = “tutorialspoint”
ผลผลิต −
1
คำอธิบาย − ในสตริงที่กำหนด "tutorialspoint" อักขระพิเศษตัวแรกที่ไม่ซ้ำกันคือ 'u' ซึ่งมีดัชนี '1' ดังนั้นเราจะคืนค่า '1' เป็นเอาต์พุต
อินพุต-2 −
s = “aaasttarrs”
ผลผลิต −
-1
คำอธิบาย − ในสตริงที่กำหนด “aaasttarrs” ไม่มีอักขระเฉพาะ ดังนั้น เราจะคืนค่าผลลัพธ์เป็น '-1'
แนวทางที่ใช้ในการแก้ปัญหานี้
ในการค้นหาดัชนีของอักขระที่ไม่ซ้ำตัวแรกในสตริงที่กำหนด เราสามารถใช้ hashmap . แนวคิดคือต้องอ่านอักขระทั้งหมดของสตริง และสร้าง hashmap โดยคีย์เป็นอักขระและค่าตามที่เกิดขึ้น
ขณะสำรวจผ่านอักขระแต่ละตัวของสตริง เราจะจัดเก็บข้อมูลการปรากฏของอักขระแต่ละตัวหากปรากฏ จะใช้เวลาเชิงเส้น O(n) ในการจัดเก็บการเกิดขึ้นของอักขระแต่ละตัว จากนั้นเราจะเข้าสู่ hashmap และจะตรวจสอบว่ามีอักขระตัวใดที่มีความถี่น้อยกว่า 2 หรือเท่ากับ '1' และเราจะคืนค่าดัชนีของอักขระนั้น ๆ
-
รับสตริง 's' เป็นอินพุต
-
ฟังก์ชัน Integer uniqueChar(string str) รับสตริงเป็นอินพุตและส่งกลับดัชนีของอักขระที่ไม่ซ้ำตัวแรกที่ปรากฏขึ้น
-
วนซ้ำบนสตริงและสร้าง hashmap ของ char และการเกิดขึ้นในขณะที่อ่านอักขระแต่ละตัวของสตริง
-
หากมีอักขระที่มีความถี่น้อยกว่า 2 หรือเท่ากับ 1 ให้คืนค่าดัชนีของอักขระนั้น
-
หากไม่มีอักขระเฉพาะอยู่ในสตริง ให้คืนค่า '-1' เป็นเอาต์พุต
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int uniqueChar(string str){
int ans = -1;
unordered_map<char,int>mp;
for(int i=0;str[i]!='\0'){
mp[str[i]]++;
}
for(int i=0;i<s.size();i++){
for(auto it= mp.begin();it!=mp.end();it++){
if(it->first==str[i] && it->second==1){
ans= i;
}
}
}
return ans;
}
int main(){
string s= "tutorialspoint";
cout<<uniqueChar(s)<<endl;
return 0;
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะพิมพ์ผลลัพธ์เป็น
1
คำอธิบาย − สตริงอินพุต 'tutorialspoint' มีอักขระเฉพาะเช่น 'u', 'r' และ 'l' และอักขระเฉพาะตัวแรก 'u' มีดัชนี '1' ดังนั้นเราจึงได้ '1' เป็นผลลัพธ์
