โจทย์
ครูพิมพ์คะแนนสอบย่อยลงในโปรแกรม และปิดท้ายรายการด้วยเลขติดลบใดก็ได้ ซึ่งเป็นสัญญาณหยุด ไม่ใช่คะแนน โปรแกรมต้องรายงานคะแนนที่อยู่ตรงกลางตามลำดับที่พิมพ์เข้ามา (คะแนนไม่ได้เรียงลำดับไว้) ถ้ามีคะแนน k ตัว ตัวตรงกลางจะอยู่ที่ตำแหน่ง k / 2 ปัดเศษลง โดยนับตำแหน่งเริ่มจาก 0 ดังนั้นถ้าจำนวนคะแนนเป็นเลขคู่ ตัวตรงกลางคือตัวที่สองจากสองตัวกลาง
จงเขียน middle_item(values)
อินพุต
values: ตัวเลขตามลำดับที่พิมพ์ การอ่านจะหยุดที่เลขติดลบตัวแรก โดยไม่สนใจตัวนั้นและทุกตัวที่อยู่หลังจากนั้น ถ้าไม่มีเลขติดลบเลย ทุกค่าถือเป็นคะแนน
เอาต์พุต
คืนค่าคะแนนที่อยู่ตรงกลาง ถ้าไม่มีคะแนนเลยก่อนถึงสัญญาณหยุด ให้คืนค่า -1
เงื่อนไข
0 ≤ ความยาวของ values ≤ 1000
−1000 ≤ แต่ละค่า ≤ 1000
ตัวอย่าง
อินพุต:
values = [88, 72, 95, 60, 81, -1]
ผลลัพธ์ที่คาดหวัง:
expected = 95
อินพุต:
std::vector<long long> values = {88, 72, 95, 60, 81, -1};
ผลลัพธ์ที่คาดหวัง:
long long expected = 95;
อินพุต:
long[] values = new long[] {88, 72, 95, 60, 81, -1};
ผลลัพธ์ที่คาดหวัง:
long expected = 95;
คำอธิบาย
คะแนนคือ 88, 72, 95, 60, 81 มีทั้งหมด 5 ตัว ตัวตรงกลางจึงอยู่ที่ตำแหน่ง 2 ซึ่งก็คือ 95
อินพุต:
values = [10, 20, 30, 40, -5, 50]
ผลลัพธ์ที่คาดหวัง:
expected = 30
อินพุต:
std::vector<long long> values = {10, 20, 30, 40, -5, 50};
ผลลัพธ์ที่คาดหวัง:
long long expected = 30;
อินพุต:
long[] values = new long[] {10, 20, 30, 40, -5, 50};
ผลลัพธ์ที่คาดหวัง:
long expected = 30;
คำอธิบาย
การอ่านหยุดที่ −5 เหลือคะแนน 4 ตัว ตำแหน่ง 2 คือ 30
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
คัดลอกค่าลงในลิสต์ใหม่ไปเรื่อย ๆ จนกว่าจะเจอเลขติดลบตัวแรก
คำใบ้ 2
ถ้ามี k ตัว ดัชนีตรงกลางคือ k / 2 โดยใช้การหารแบบจำนวนเต็ม
คำใบ้ 3
ถ้าไม่ได้คัดลอกอะไรเลย ก็ไม่มีค่าตรงกลาง
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน