[ข้อกำหนดคำถาม] ให้หมายเลข n และ n ตอนนี้คุณต้องหาจำนวนที่เกิดขึ้นมากกว่า 50% ของเวลาในพื้นที่ O (n) ภายใน O (1)
[เริ่มพล่าม] ในตอนแรกฉันเห็นคำถามนี้ตาบอดทันที (tot)/~~~ (.*) หากมีเพียงความต้องการเวลาของ O (n) มันสามารถแก้ไขได้ทันทีด้วยแฮช (นั่นคือมีพื้นที่ว่าง) และดูเหมือนยากที่จะแก้พื้นที่ของ O (1)
[คิดว่า 1] คู่วนซ้ำนี่เป็นวิธีที่มีประสิทธิภาพน้อยที่สุดในการแก้ปัญหานี้นั่นคือคำนวณจำนวนครั้งที่ปรากฏสำหรับแต่ละหมายเลขและความซับซ้อนของเวลา o (n^2) ออกโดยตรง
[คิด 2] การเรียงลำดับก่อนให้จัดเรียงหมายเลขที่คล้ายกันเข้าด้วยกันแล้วสำรวจจากหมายเลขแรก ตอนนี้ยกตัวอย่างเช่น: 10,00012 ตอนนี้เรียงลำดับ: 0000112 เริ่มจาก 0 ตั้งค่าตัวนับ t = 0 ตอนนี้มี 4 0s จากนั้น t = 4 พบว่ามากกว่าครึ่งหนึ่งของพวกเขาเอาท์พุท 0 วิธีนี้เป็นรุ่นที่เหมาะสมที่สุดของวิธีก่อนหน้า
[คิดว่า 3] มันเป็นความคิดในการแลกเปลี่ยนพื้นที่สำหรับเวลาและการแฮชเพื่อให้อาร์เรย์หนึ่งมิติมีสองความหมาย ตัวอย่างเช่น A [x] = y แสดงว่าหมายเลข x ปรากฏขึ้น y ครั้ง ความซับซ้อนของเวลาของวิธีนี้คือ o (n) แต่พื้นที่เป็นจริง ... ฉันจะไม่พูดถึงมัน (* ￣￣) ออก
[ความคิด 4] ก่อนคำนวณความน่าจะเป็นเลือกจำนวนตัวเลขเหล่านี้ที่มีแนวโน้มที่จะตอบสนองความต้องการมากที่สุดจากนั้นสุ่มเลือกสองสามตัว นี่ ... ลืมมันไป
[ความคิด 5] หัวข้อของวันนี้เป็นอัลกอริทึม MJRTY ที่เรียกว่าหรือที่เรียกว่าอัลกอริทึมการลงคะแนนส่วนใหญ่ แนวคิดหลักมีดังนี้: (ความซับซ้อนของอัลกอริทึมนี้คือ o (n)! ไม่จำเป็นต้องมีการจัดเก็บเพิ่มเติมในอวกาศดังนั้นความซับซ้อนของพื้นที่คือ O (1) !!!)
ถ้านับ == 0 ให้ตั้งค่าการโหวตเป็นองค์ประกอบปัจจุบันของอาร์เรย์และกำหนดนับเป็น 1;
มิฉะนั้นหากโหวตและองค์ประกอบอาร์เรย์มีค่าเท่ากันนับ ++ มิฉะนั้นนับ
ทำซ้ำสองขั้นตอนข้างต้นจนกว่าจะมีการสแกนอาร์เรย์
Count ถูกกำหนดให้เป็น 0 และสแกนอาร์เรย์อีกครั้งตั้งแต่ต้น หากค่าขององค์ประกอบอาร์เรย์เหมือนกับค่าของการโหวตให้นับ ++ จนกว่าจะมีการสแกนอาร์เรย์
หากค่าของการนับมากกว่าหรือเท่ากับ n/2 ในเวลานี้ค่าของการโหวตจะถูกส่งคืนมิฉะนั้น -1 จะถูกส่งคืน;
ต่อไปนี้คือการใช้รหัส เนื่องจากคำถามทำให้มั่นใจได้ว่าผลลัพธ์จะต้องมีอยู่เราจึงละเว้นขั้นตอนสุดท้ายของการตรวจสอบและตรวจสอบ
รหัสคีย์มีดังนี้:
#include <Iostream> การใช้ Namespace std; int len; เป็นโมฆะค้นหา (int* a, int n) {char aptidate; int ntimes, i; สำหรับ (i = ntimes = 0; i <n; i ++) {ถ้า (ntimes == 0) ผู้สมัคร = a [i], ntimes = 1; } int main () {cin >> len; int a [len]; สำหรับ (int i = 0; i <n; i ++) cin >> a [i]; ค้นหา (a, len); ระบบ ("หยุด"); return 0;}ข้างต้นคือจำนวนมากกว่าครึ่ง (50%) ของจำนวนเหตุการณ์ที่แนะนำให้คุณทราบโดยบรรณาธิการ ฉันหวังว่ามันจะเป็นประโยชน์กับคุณ หากคุณมีคำถามใด ๆ โปรดฝากข้อความถึงฉันและบรรณาธิการจะตอบกลับคุณทันเวลา ขอบคุณมากสำหรับการสนับสนุนเว็บไซต์ Wulin.com!