กลับไปยังโจทย์
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ตัวอักษรที่ไม่ซ้ำตัวแรก

หาตัวอักษรตัวแรกที่ปรากฏเพียงครั้งเดียว

สิ่งที่คุณจะได้เรียนรู้

  • นับอักขระด้วยดิกชันนารี
  • ไล่รอบที่สองเพื่อหาตัวแรกที่ไม่ซ้ำ
  • แก้ปัญหาในเวลาเชิงเส้น

โจทย์

คืนค่าดัชนีของตัวอักษรตัวแรกใน text ที่ปรากฏเพียงครั้งเดียว (เปรียบเทียบตัวพิมพ์เล็ก-ใหญ่)

ให้เขียนฟังก์ชัน first_unique_index(text)

อินพุต

text: ข้อความที่ต้องการตรวจสอบ

เอาต์พุต

คืนค่าดัชนีของตัวอักษรที่พบ หรือ -1 หากไม่มีตัวอักษรใดที่ไม่ซ้ำเลย

เงื่อนไข

0 ≤ ความยาว ≤ 100,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
text = "swiss"

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
std::string text = "swiss";

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
string text = "swiss";

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

s ซ้ำ, w ปรากฏครั้งเดียวที่ดัชนี 1

ตัวอย่างที่ 2
อินพุต:
text = "aabb"

ผลลัพธ์ที่คาดหวัง:
expected = -1
อินพุต:
std::string text = "aabb";

ผลลัพธ์ที่คาดหวัง:
long long expected = -1;
อินพุต:
string text = "aabb";

ผลลัพธ์ที่คาดหวัง:
long expected = -1;

คำอธิบาย

ทุกตัวอักษรซ้ำหมด: -1

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ต้องหาอักขระที่ปรากฏแค่ครั้งเดียว ไม่ใช่แค่ตัวที่ต่างตัวแรก

คำใบ้ 2

นับความถี่ของอักขระทั้งหมดก่อน แล้วค่อยหา index แรกที่มีความถี่เป็นหนึ่ง

คำใบ้ 3

อย่าลืมว่าอักษรตัวใหญ่กับตัวเล็กถือเป็นคนละอักขระ

ความซับซ้อนที่คาดหวัง

เวลา O(n), หน่วยความจำเพิ่ม O(k)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก