Array algorithms: max, count, search, average
งานคลาสสิกของอาร์เรย์สี่อย่าง
- งานกับอาร์เรย์ส่วนใหญ่เป็นหนึ่งในการสแกนสี่แบบ: หา ค่าสูงสุด, นับ จำนวนตรงกัน, ค้นหา ค่า หรือหา ค่าเฉลี่ย
- แต่ละอย่างเป็นการวนลูป
forเดียวบนอาร์เรย์ พร้อมตัวแปรที่จดจำสิ่งบางอย่างไว้ - เมื่อคุณรู้เรื่องสี่อย่างนี้แล้ว ปัญหาส่วนใหญ่เกี่ยวกับอาร์เรย์ก็เพียงการปรับเล็กน้อยจากหนึ่งในสี่สิ่งนี้
การหาค่าสูงสุด
- เริ่มต้นด้วยการสมมติว่ารายการ แรกสุดมีค่ามากที่สุด:
int best = a[0]; - จากนั้นดูรายการที่เหลือ ถ้ารายการไหนมีค่ามากกว่า
bestมันจะกลายเป็นbestใหม่ - วิธีนี้ใช้ได้กับเลขลบด้วย เพราะเราเริ่มจากรายการจริง ไม่ใช่
0
Counting with a condition
- เคาน์เตอร์ เริ่มที่
0และเพิ่ม1ทุกครั้งที่รายการผ่านเงื่อนไข - เช่นตัวอย่าง นับเลขคู่โดยการทดสอบ
a[i] % 2 == 0ภายในวนลูป - ค่าสุดท้ายของเคาน์เตอร์คือคำตอบของคุณ
การค้นหาแบบเชิงเส้น
- เพื่อ ค้นหา ให้เดินผ่านอาร์เรย์และเปรียบเทียบแต่ละรายการกับเป้าหมาย
- คืนค่า ดัชนี ทันทีที่พบการจับคู่ ถ้าวนลูปจบโดยไม่พบ ให้คืนค่า
-1 -1เป็นสัญญาณ "ไม่พบ" ที่นิยมใช้เพราะมันไม่เคยเป็นดัชนีที่ถูกต้อง
ค่าเฉลี่ยโดยไม่เกิดข้อผิดพลาดจากการหารจำนวนเต็ม
- รวมรายการทั้งหมดลงในผลรวม
intแล้วหารด้วยn - การหาร
intสองตัวจะทำให้ทศนิยมหายไป ดังนั้นต้อง cast:(double)total / n - คืนค่า
doubleเพื่อให้ผู้เรียกได้รับค่าเฉลี่ยที่แม่นยำ
ข้อผิดพลาดที่พบบ่อย
- เริ่มหาค่าสูงสุดหรือต่ำสุดจากองค์ประกอบแรก แล้วจึงเปรียบเทียบส่วนที่เหลือ
- อย่าอ่านข้ามขอบเขตของอาร์เรย์
ลองดูเลย
- ส่งอาร์เรย์และความยาว
nและเลือกตัวแปรสำหรับ "การจดจำ" ที่เหมาะสมสำหรับแต่ละงาน - อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Scanning an array
หนึ่งรอบผ่านรักษา ผลลัพธ์สะสม (max, sum, count) Across array
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม int max(const int a[], int n) เพื่อให้ส่งค่าสูงสุด (สมมติว่า n >= 1) เริ่มจาก a[0] เพื่อรองรับค่าลบ ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม int count_even(const int a[], int n) นับจำนวนอู่ Even ใช้ % 2 ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม int index_of(const int a[], int n, int target) ส่งค่า index ของ target ตัวแรก หรือ -1 ถ้าไม่มี ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม double average(const int a[], int n) เพื่อส่งคืนค่าเฉลี่ยของรายการ (สมมติ n >= 1) Cast เพื่อหลีกเลี่ยงการหารจำนวนเต็ม อย่า เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่