ต่อไปนี้เป็นวิธีการสองสามวิธีในการแนะนำจำนวนหมายเลขอาร์เรย์ Java ให้คุณ เนื้อหาเฉพาะมีดังนี้:
วิธีที่ 1:
การเรียงลำดับอาเรย์จากนั้นค่ากลางจะเป็นค่าที่จะพบได้อย่างแน่นอน เรียงลำดับความซับซ้อนของเวลาขั้นต่ำ (เรียงลำดับอย่างรวดเร็ว) O (nlogn) รวมถึงการสำรวจ
วิธีที่ 2:
การใช้วิธีการแฮชตารางนั่นคือการนับจำนวนเหตุการณ์ที่เกิดขึ้นของแต่ละอาร์เรย์และตัวเลขที่ส่งออกซึ่งมีค่ามากกว่าความยาวของอาร์เรย์
วิธีที่ 3:
จำนวนเหตุการณ์ที่เกิดขึ้นเกินครึ่งหนึ่งของความยาวของอาร์เรย์แสดงให้เห็นว่าตัวเลขนี้จะปรากฏขึ้นมากกว่าผลรวมของตัวเลขอื่น ๆ
พิจารณาการลบตัวเลขที่แตกต่างกันสองตัวในแต่ละครั้งจำนวนเหตุการณ์ที่เกิดขึ้นในตัวเลขที่เหลือยังคงเกินจำนวนทั้งหมด ทำซ้ำกระบวนการอย่างต่อเนื่องไม่รวมตัวเลขอื่น ๆ และในที่สุดก็พบจำนวนที่มีมากกว่าครึ่งหนึ่งของเหตุการณ์ ความซับซ้อนของเวลาของวิธีนี้คือ o (n) และความซับซ้อนของพื้นที่คือ O (1)
เพื่อเปลี่ยนความคิดสิ่งนี้สามารถทำได้ผ่านการนับมากกว่าการลบทางกายภาพที่แท้จริง ในระหว่างกระบวนการสำรวจอาร์เรย์บันทึกสองค่าหนึ่งคือหมายเลขในอาร์เรย์และอีกอันคือจำนวนเหตุการณ์ที่เกิดขึ้น เมื่อข้ามไปยังหมายเลขถัดไปหากหมายเลขนี้เหมือนกับหมายเลขที่บันทึกไว้ก่อนหน้านี้จำนวนครั้งจะเพิ่มขึ้น 1 และหากแตกต่างกันจำนวนครั้งจะลดลง 1 ถ้าจำนวนครั้งคือ 0 ให้บันทึกตัวเลขถัดไป
public int morehalf (int [] nums) {int result = 0; int count = 1; ถ้า (nums.length == 0) return -1; result = nums [0]; สำหรับ (int i = 1; i <nums.length; i ++) {ถ้า (count == 0) ผลลัพธ์;}วิธีที่ 4:
ปรับปรุงการเรียงลำดับแถวด่วนที่กล่าวถึงก่อนหน้านี้หากอาร์เรย์ถูกเรียงลำดับตัวเลขในตำแหน่งกลางจะต้องเป็นค่าที่คุณต้องการ ความซับซ้อนของเวลาของอาร์เรย์การเรียงลำดับคือ o (nlog (n)) แต่สำหรับคำถามนี้มีอัลกอริทึมที่ดีกว่าที่สามารถพบได้ภายในความซับซ้อนของเวลา o (n)
มาจากอัลกอริทึมการเรียงลำดับที่รวดเร็ววิธีพาร์ติชัน () เป็นวิธีที่สำคัญที่สุด วิธีนี้ส่งคืนดัชนีซึ่งสามารถมั่นใจได้ว่าหมายเลขที่ตำแหน่งดัชนีจะถูกเรียงลำดับ จำนวนทางด้านซ้ายของดัชนีมีขนาดเล็กกว่าจำนวนที่ดัชนีอยู่และตัวเลขทางด้านขวาของดัชนีมีขนาดใหญ่กว่าตัวเลขที่ดัชนีอยู่ จากนั้นคำถามนี้สามารถแก้ไขได้โดยใช้แนวคิดนี้
ดัชนีส่งคืนผ่านพาร์ติชัน () หากดัชนี == กลางหมายความว่าค่ามัธยฐานของอาเรย์ถูกค้นพบ; หาก indexmid หมายความว่าค่ามัธยฐานอยู่ระหว่าง [start, index-1] ฉันรู้ว่าได้รับการสิ้นสุดของดัชนี == Mid Loop
พาร์ติชั่น int สาธารณะ (int [] nums, int start, int end) {int pivotkey = nums [start]; int Origin = start; ในขณะที่ (start <end) {ในขณะที่ (start <end && nums [end]> = pivotkey) สิ้นสุด-; swap (nums, start, end); swap (nums, ต้นกำเนิด, end); return end;} p int [] swap (int [] ints, int x, int y) {int temp = ints [x]; ints [x] = ints [y]; ints [y] = อุณหภูมิ; กลับ ints; } public int morethanhalf (int [] nums) {ถ้า (nums.length == 0) return -1; int start = 0; int end = nums.length-1; int index = พาร์ติชัน (nums, start, end) int mid = nums.length/2; พาร์ติชัน (NUMS, Start, INDEX-1); ELSE {// มิฉะนั้นปรับดัชนีอาร์เรย์ของดัชนี+1 ถึงส่วนท้าย = พาร์ติชัน (NUMS, INDEX+1, สิ้นสุด);}} ส่งคืน NUMS [ดัชนี];}เนื้อหาข้างต้นแนะนำเนื้อหาที่เกี่ยวข้องของรหัส Java ที่ใช้ตัวเลขที่ปรากฏมากกว่าครึ่งหนึ่งของเวลาในอาร์เรย์ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน!