โจทย์
คืนค่าที่มีค่ามากเป็นอันดับสองที่ไม่ซ้ำกันในลิสต์ ค่าที่ซ้ำกันให้นับเพียงครั้งเดียว
ให้เขียนฟังก์ชัน second_largest(numbers)
อินพุต
numbers: ลิสต์ของจำนวนเต็มที่ไม่ติดลบ
เอาต์พุต
คืนค่าที่มีค่ามากเป็นอันดับสองที่ไม่ซ้ำกัน หรือ -1 หากไม่มีค่าดังกล่าว
เงื่อนไข
0 ≤ ความยาว ≤ 100,000; 0 ≤ แต่ละค่า ≤ 10⁹
ตัวอย่าง
อินพุต:
numbers = [4, 9, 7, 9]
ผลลัพธ์ที่คาดหวัง:
expected = 7
อินพุต:
std::vector<long long> numbers = {4, 9, 7, 9};
ผลลัพธ์ที่คาดหวัง:
long long expected = 7;
อินพุต:
long[] numbers = new long[] {4, 9, 7, 9};
ผลลัพธ์ที่คาดหวัง:
long expected = 7;
คำอธิบาย
ค่าที่ไม่ซ้ำกันคือ 9, 7, 4; ค่ามากเป็นอันดับสองคือ 7
อินพุต:
numbers = [5, 5]
ผลลัพธ์ที่คาดหวัง:
expected = -1
อินพุต:
std::vector<long long> numbers = {5, 5};
ผลลัพธ์ที่คาดหวัง:
long long expected = -1;
อินพุต:
long[] numbers = new long[] {5, 5};
ผลลัพธ์ที่คาดหวัง:
long expected = -1;
คำอธิบาย
มีค่าไม่ซ้ำกันเพียงค่าเดียว ดังนั้นคำตอบคือ -1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ต้องการค่ามากสุดและค่าถัดไปที่ไม่ซ้ำ ไม่ใช่แค่สองตำแหน่งแรก
คำใบ้ 2
เก็บ maximum สองค่าที่ต่างกันขณะไล่ดู และอัปเดตเมื่อค่าใหม่อยู่เหนือหรือคั่นกลางได้
คำใบ้ 3
ถ้าไม่เคยมีค่าที่ต่างกันเป็นอันดับสอง ให้คืนค่า fallback พิเศษ
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน