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