บทความนี้อธิบายการดำเนินการเลือกเวลาเชิงเส้นที่ใช้โดย Java ตามอัลกอริทึมการแบ่งพาร์ติชันและพิชิต แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
ปัญหาการเลือกเวลาเชิงเส้น: องค์ประกอบ N และจำนวนเต็ม k, 1≤k≤nมันจำเป็นต้องค้นหาองค์ประกอบที่เล็กที่สุดขององค์ประกอบ N เหล่านี้ (ชุดเชิงเส้นที่กำหนดที่นี่ไม่เป็นระเบียบ)
การเลือกเชิงเส้นแบ่งแบบสุ่ม
วิธีการสุ่มการเลือกเวลาเชิงเส้นสามารถเลียนแบบการออกแบบอัลกอริทึมการเรียงลำดับแบบสุ่ม แนวคิดพื้นฐานคือการแบ่งอาร์เรย์อินพุตซ้ำ ซึ่งแตกต่างจากการเรียงลำดับอย่างรวดเร็วมันจะประมวลผลเฉพาะหนึ่งใน subarrays ที่แบ่งออก
โปรแกรมคำอธิบาย: ใช้ฟังก์ชั่นสุ่มเพื่อสร้างเกณฑ์มาตรฐานแบ่งหารอาร์เรย์ A [P: R] ออกเป็นสอง subarrays A [P: I] และ A [i+1: R] ดังนั้นแต่ละองค์ประกอบใน [P: I] ไม่ยิ่งใหญ่กว่าแต่ละองค์ประกอบใน A [i+1: R] จากนั้น "j = i-p+1" คำนวณจำนวนองค์ประกอบ j ใน [p: i] ถ้า k <= j ดังนั้นองค์ประกอบที่เล็กที่สุด k-th ใน A [P: R] อยู่ใน sub-array a [p: i] และถ้า k> j องค์ประกอบที่เล็กที่สุด k-th อยู่ใน sub-array a [i+1: r] หมายเหตุ: เนื่องจากเป็นที่ทราบกันดีว่าองค์ประกอบใน sub-array a [p: i] ทั้งหมดมีขนาดเล็กกว่าองค์ประกอบเล็ก ๆ k-th ที่จะพบองค์ประกอบ k-th ขนาดเล็กใน A [P: R] ที่จะพบคือองค์ประกอบเล็ก ๆ K-th ใน [i+1: r]
ในกรณีที่เลวร้ายที่สุดตัวอย่างเช่นเมื่อพบองค์ประกอบที่เล็กที่สุดเสมอมันจะถูกแบ่งออกเป็นองค์ประกอบที่ใหญ่ที่สุดเสมอซึ่งเป็นความซับซ้อนของเวลาของ O (n^2) อย่างไรก็ตามความซับซ้อนของเวลาโดยเฉลี่ยนั้นเกี่ยวข้องกับ N เป็นเส้นตรงซึ่งก็คือ O (n)
แพ็คเกจคณิตศาสตร์; นำเข้า java.util.scanner; นำเข้า java.util.random; คลาสสาธารณะแบบสุ่ม {โมฆะคงที่สาธารณะ swap (int x, int y) {int temp = x; x = y; y = อุณหภูมิ; } การสุ่ม int สาธารณะ (int x, int y) {สุ่มสุ่ม = ใหม่สุ่ม (); int num = random.nextint (y)%(y - x + 1) + x; กลับมา; } พาร์ทิชัน INT สาธารณะ (int [] รายการ, int ต่ำ, int สูง) {int tmp = list [ต่ำ]; // อันแรกของอาร์เรย์คือแกนกลางในขณะที่ (ต่ำ <สูง) {ในขณะที่ (ต่ำ <high && รายการ [สูง]> tmp) {สูง-; } รายการ [ต่ำ] = รายการ [สูง]; // บันทึกที่เล็กกว่าแกนกลางจะถูกย้ายไปที่ระดับต่ำสุดในขณะที่ (ต่ำ <high && list [ต่ำ] <tmp) {ต่ำ ++; } รายการ [สูง] = รายการ [ต่ำ]; // บันทึกที่ใหญ่กว่าแกนกลางถูกย้ายไปยังรายการระดับสูง} [ต่ำ] = tmp; // บันทึกที่ใหญ่กว่าแกนกลางจะถูกส่งกลับต่ำ // กลับไปที่ตำแหน่งของแกนกลาง} public int randomizedPartition (int [] อาร์เรย์, int ซ้าย, int ขวา) {int i = สุ่ม (ซ้าย, ขวา); swap (อาร์เรย์ [i], อาร์เรย์ [ซ้าย]); พาร์ติชันส่งคืน (อาร์เรย์ซ้ายขวา); } public int randomizedSelect (int [] อาร์เรย์, int ซ้าย, int ขวา, int k) {ถ้า (ซ้าย == ขวา) {return array [ซ้าย]; } int i = แบบสุ่ม (อาร์เรย์, ซ้าย, ขวา); int j = i - ซ้าย + 1; if (k <= j) {return selectelect (อาร์เรย์, ซ้าย, i, k); } else {return randomizedSelect (อาร์เรย์, i+1, ขวา, kj); }} โมฆะคงที่สาธารณะหลัก (สตริง args []) {system.out.println ("ผลการทดสอบ wulin.com:"); int [] a = {7,5,3,4,8,6,9,1,1,2}; สำหรับ (int i = 0; i <9; i ++) {system.out.print (a [i]+""); } system.out.println (); RandomSelect r = new RandomSelect (); System.out.println ("องค์ประกอบที่เล็กที่สุดคุณต้องการสอบถามในอาร์เรย์?"); @suppresswarnings ("ทรัพยากร") สแกนเนอร์ sc = เครื่องสแกนใหม่ (System.in); int m = sc.nextint (); int n = r.randomizedSelect (a, 0,8, m); System.out.println ("th" ในอาร์เรย์นี้ " + m +" องค์ประกอบที่เล็กที่สุดคือ: " + n); -ผลการทำงาน:
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน