ในการสัมภาษณ์อัลกอริทึมผู้สัมภาษณ์มักจะทำบทความเกี่ยวกับรายการที่เชื่อมโยงการเรียงลำดับต้นไม้ไบนารีและการค้นหาแบบไบนารีและคนส่วนใหญ่สามารถติดตามหนังสือมืออาชีพเพื่อจดจำพวกเขา ผู้สัมภาษณ์ไม่ต้องการรับสมัครโปรแกรมเมอร์ที่มีทักษะความจำที่ดี แต่ไม่สามารถเรียนรู้และนำไปใช้ได้ ดังนั้นจึงเป็นสิ่งสำคัญมากที่จะเรียนรู้ที่จะสร้างแบบจำลองและวิเคราะห์ปัญหาทางคณิตศาสตร์และใช้อัลกอริธึมที่สมเหตุสมผลหรือโครงสร้างข้อมูลเพื่อแก้ปัญหา
คำถามสัมภาษณ์: พิมพ์จำนวนขั้นต่ำของอาร์เรย์หมุน
ชื่อเรื่อง: ย้ายองค์ประกอบหลายอย่างแรกของอาร์เรย์ไปยังจุดสิ้นสุดของอาร์เรย์ซึ่งเราเรียกว่าการหมุนของอาร์เรย์ ป้อนการหมุนของอาร์เรย์ที่เรียงลำดับเพิ่มขึ้นและส่งออกองค์ประกอบขั้นต่ำของอาร์เรย์การหมุน ตัวอย่างเช่นอาร์เรย์ {3, 4, 5, 1, 2} คือการหมุนของอาร์เรย์ {1, 2, 3, 4, 5} และค่าต่ำสุดของอาร์เรย์คือ 1
เพื่อให้บรรลุข้อกำหนดนี้เราเพียงแค่ต้องสำรวจอาร์เรย์ค้นหาค่าที่เล็กที่สุดและออกจากลูปโดยตรง การใช้งานรหัสมีดังนี้:
ระดับสาธารณะ test08 {สาธารณะคงที่ int getTheMin (int nums []) {ถ้า (nums == null || nums.length == 0) {โยน runtimeException ใหม่ ("ข้อผิดพลาดอินพุต!"); } int result = nums [0]; สำหรับ (int i = 0; i <nums.length - 1; i ++) {ถ้า (nums [i + 1] <nums [i]) {result = nums [i + 1]; หยุดพัก; }} ผลการส่งคืน; } โมฆะคงที่สาธารณะหลัก (String [] args) {// อินพุตทั่วไปการหมุนของอาร์เรย์ monotonic จากน้อยไปมาก int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่เล็กที่สุดซึ่งเป็นเพียงจำนวนที่เล็กที่สุด int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // มีตัวเลขที่ซ้ำกัน แต่ตัวเลขที่ซ้ำกันไม่ใช่ตัวเลขแรกและหมายเลขสุดท้าย int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่ซ้ำกันเกิดขึ้นเป็นหมายเลขแรกและหมายเลขสุดท้าย int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // monotone array จากน้อยไปมาก, หมุน 0 องค์ประกอบนั่นคืออาร์เรย์ monotonic จากน้อยไปมากเอง int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // มีเพียงหมายเลขเดียวในอาร์เรย์ int [] array6 = {2}; System.out.println (getthemin (array6)); // ตัวเลขในอาร์เรย์เป็น int เดียวกัน [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); -ไม่มีอะไรผิดปกติกับผลการพิมพ์ อย่างไรก็ตามวิธีนี้ไม่ได้ดีที่สุด มาดูกันว่ามีวิธีการหาวิธีที่ดีกว่าในการจัดการกับมันหรือไม่
เป็นระเบียบยังต้องค้นหา?
เมื่อเราพบคำหลักทั้งสองนี้เราจะนึกถึงวิธีการค้นหาแบบไบนารีของเราอย่างหลีกเลี่ยงไม่ได้ แต่เพื่อนหลายคนจะถามว่าอาร์เรย์ของเราไม่ได้เป็นอาร์เรย์ที่ได้รับคำสั่งอย่างแท้จริงอีกต่อไปหลังจากถูกหมุน เราสามารถคิดแบบนี้ได้
เราสามารถตั้งค่าตัวห้อยสองตัวต่ำและสูงและตั้งค่า mid = (ต่ำ + สูง)/2 และเราสามารถค้นหาอาร์เรย์องค์ประกอบ [กลาง] ที่อยู่ตรงกลางของอาร์เรย์ หากองค์ประกอบกลางอยู่ในอาร์เรย์ที่เพิ่มขึ้นด้านหน้าก็ควรจะมากกว่าหรือเท่ากับองค์ประกอบที่สอดคล้องกันของตัวห้อยต่ำ ในเวลานี้องค์ประกอบที่เล็กที่สุดในอาร์เรย์ควรอยู่ด้านหลังองค์ประกอบ เราสามารถชี้ตัวห้อยต่ำไปยังองค์ประกอบระดับกลางซึ่งสามารถ จำกัด ช่วงของการค้นหาได้
ในทำนองเดียวกันหากองค์ประกอบระดับกลางอยู่ใน subarray ที่เพิ่มขึ้นในภายหลังควรน้อยกว่าหรือเท่ากับองค์ประกอบที่สอดคล้องกับตัวห้อยสูง ในเวลานี้องค์ประกอบที่เล็กที่สุดในอาร์เรย์ควรอยู่ด้านหน้าขององค์ประกอบกลาง เราสามารถอัปเดตตัวห้อยสูงไปยังตัวห้อยเฉลี่ยซึ่งสามารถ จำกัด ช่วงการค้นหาให้แคบลง องค์ประกอบที่สอดคล้องกับตัวห้อยสูงหลังจากการเคลื่อนที่ยังคงอยู่ใน subarray ที่เพิ่มขึ้นตามมา
ไม่ว่าจะเป็นการอัปเดตต่ำหรือสูงช่วงการค้นหาของเราจะลดลงเหลือครึ่งหนึ่งของต้นฉบับ ต่อไปเราจะใช้ตัวห้อยที่อัปเดตเพื่อทำซ้ำการค้นหารอบใหม่ จนกระทั่งสองตัวห้อยสุดท้ายอยู่ติดกันนั่นคือเงื่อนไขการสิ้นสุดลูปของเรา
ฉันได้พูดมากและดูเหมือนว่าฉันจะยุ่งเหยิง เราอาจใช้อินพุตในคำถามเพื่อจำลองและตรวจสอบอัลกอริทึมของเรา
มาดูวิธีการใช้แนวคิดนี้ใน Java โดยใช้รหัส:
ระดับสาธารณะ test08 {สาธารณะคงที่ int getTheMin (int nums []) {ถ้า (nums == null || nums.length == 0) {โยน runtimeException ใหม่ ("ข้อผิดพลาดอินพุต!"); } // หากมีเพียงองค์ประกอบเดียวให้ส่งคืนโดยตรงถ้า (nums.length == 1) ส่งคืน nums [0]; int result = nums [0]; int low = 0, high = nums.length - 1; int กลาง; // ตรวจสอบให้แน่ใจว่าค่าที่สอดคล้องกับตัวห้อยต่ำอยู่ใน subarray ที่เพิ่มขึ้นทางด้านซ้ายและค่าที่สอดคล้องกับสูงอยู่ใน subarray ที่เพิ่มขึ้นทางด้านขวาในขณะที่ (nums [ต่ำ]> = nums [สูง]) {// ตรวจสอบให้แน่ใจ } // ใช้ตำแหน่งกลางกลาง = (ต่ำ + สูง) / 2; // ระบุว่าองค์ประกอบกลางจะเพิ่มขึ้นทางด้านซ้ายถ้า (nums [mid]> = nums [ต่ำ]) {low = mid; } else {high = mid; }} ผลการส่งคืน; } โมฆะคงที่สาธารณะหลัก (String [] args) {// อินพุตทั่วไปการหมุนของอาร์เรย์ monotonic จากน้อยไปมาก int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่เล็กที่สุดที่เพิ่งทำซ้ำตัวเลขคือ int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // มีตัวเลขที่ซ้ำกัน แต่ตัวเลขที่ซ้ำกันไม่ใช่ตัวเลขแรกและหมายเลขสุดท้าย int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่ซ้ำกันนั้นเป็นหมายเลขแรกและหมายเลขสุดท้าย int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // อาร์เรย์จากน้อยไปมากที่น่าเบื่อ, หมุน 0 องค์ประกอบนั่นคืออาร์เรย์ที่น่าเบื่อหน่ายตัวเอง int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // มีเพียงหมายเลขเดียวในอาร์เรย์ int [] array6 = {2}; System.out.println (getthemin (array6)); // ตัวเลขในอาร์เรย์เป็น int เดียวกัน [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); // พิเศษฉันไม่ทราบวิธีการย้าย int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array8)); -เรากล่าวถึงก่อนหน้านี้ว่าในอาร์เรย์หมุนเนื่องจากตัวเลขหลายตัวในอาร์เรย์ที่เรียงลำดับเพิ่มขึ้นจะถูกย้ายไปด้านหลังอาร์เรย์หมายเลขแรกจะมากกว่าหรือเท่ากับหมายเลขสุดท้ายและมีอีกกรณีพิเศษที่มีการย้ายองค์ประกอบ 0 นั่นคืออาร์เรย์ของมันเองก็เป็นอาร์เรย์หมุนของตัวเอง สถานการณ์นี้ได้รับคำสั่งดังนั้นเราเพียงแค่ต้องส่งคืนองค์ประกอบแรกซึ่งเป็นเหตุผลที่ฉันกำหนดผลลัพธ์ให้กับ NUMS [0] ก่อน
รหัสด้านบนสมบูรณ์แบบหรือไม่? เราไม่เป็นไปตามข้อกำหนดของเราผ่านกรณีทดสอบ ลองดูที่อินพุต Array8 ในรายละเอียด ก่อนอื่นวิเคราะห์การทำงานของคอมพิวเตอร์:
แต่เราสามารถเห็นได้อย่างรวดเร็วว่าค่าต่ำสุดของเราไม่ใช่ 1 แต่ 0 ดังนั้นเมื่ออาเรย์ [ต่ำ] อาร์เรย์ [กลาง] และอาร์เรย์ [สูง] เท่ากันโปรแกรมของเราไม่ทราบวิธีการย้าย ตามวิธีการเคลื่อนไหวปัจจุบันอาร์เรย์ [กลาง] จะเพิ่มขึ้นทางด้านซ้ายโดยค่าเริ่มต้น เห็นได้ชัดว่าไม่รับผิดชอบ
แก้ไขรหัส:
ระดับสาธารณะ test08 {สาธารณะคงที่ int getTheMin (int nums []) {ถ้า (nums == null || nums.length == 0) {โยน runtimeException ใหม่ ("ข้อผิดพลาดอินพุต!"); } // หากมีเพียงองค์ประกอบเดียวให้ส่งคืนโดยตรงถ้า (nums.length == 1) ส่งคืน nums [0]; int result = nums [0]; int low = 0, high = nums.length - 1; int mid = ต่ำ; // ตรวจสอบให้แน่ใจว่าค่าที่สอดคล้องกับตัวห้อยต่ำอยู่ใน subarray ที่เพิ่มขึ้นทางด้านซ้ายและค่าที่สอดคล้องกับสูงอยู่ใน subarray ที่เพิ่มขึ้นทางด้านขวาในขณะที่ (nums [ต่ำ]> = nums [สูง]) {// ตรวจสอบให้แน่ใจ } // ใช้ตำแหน่งกลางกลาง = (ต่ำ + สูง) / 2; // ในกรณีพิเศษที่ค่าทั้งสามเท่ากันคุณต้องค้นหาค่าที่เล็กที่สุดตั้งแต่ต้นจนจบถ้า (nums [mid] == nums [ต่ำ] && nums [mid] == nums [สูง]) {return midinorder (nums, ต่ำ, สูง); } // ระบุว่าองค์ประกอบกลางจะเพิ่มขึ้นทางด้านซ้ายถ้า (nums [mid]> = nums [ต่ำ]) {low = mid; } else {high = mid; }} ผลการส่งคืน; } / *** ค้นหาค่าต่ำสุดในอาร์เรย์** @param nums array* @param start array ตำแหน่งเริ่มต้น* @param end array end ตำแหน่ง* @ @ @@return จำนวนที่น้อยที่สุดที่พบ* / public Static int midinorder (int [] nums, int start, int) {int result = nums สำหรับ (int i = start+1; i <= end; i ++) {ถ้า (ผลลัพธ์> nums [i]) ผลลัพธ์ = nums [i]; } ผลตอบแทนผลลัพธ์; } โมฆะคงที่สาธารณะหลัก (String [] args) {// อินพุตทั่วไปการหมุนของอาร์เรย์ monotonic จากน้อยไปมาก int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่เล็กที่สุดที่เพิ่งเกิดขึ้นเป็นหมายเลขที่พบบ่อยที่สุด int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // มีตัวเลขที่ซ้ำกัน แต่ตัวเลขที่ซ้ำกันไม่ใช่ตัวเลขแรกและหมายเลขสุดท้าย int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // มีตัวเลขที่ซ้ำกันและตัวเลขที่ซ้ำกันนั้นเป็นหมายเลขแรกและหมายเลขสุดท้าย int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // อาร์เรย์จากน้อยไปมากที่น่าเบื่อ, หมุน 0 องค์ประกอบนั่นคืออาร์เรย์ที่น่าเบื่อหน่ายตัวเอง int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // มีเพียงหมายเลขเดียวในอาร์เรย์ int [] array6 = {2}; System.out.println (getthemin (array6)); // ตัวเลขทั้งหมดในอาร์เรย์เป็น int เดียวกัน [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); // พิเศษฉันไม่ทราบวิธีการย้าย int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array8)); -จากนั้นเราใส่มันด้วยกรณีทดสอบที่สมบูรณ์และการทดสอบผ่าน
สรุป
ในความเป็นจริงคำถามนี้มีหลายจุดที่จะตรวจสอบ แต่ในความเป็นจริงมันคือการตรวจสอบแอปพลิเคชันที่ยืดหยุ่นของการค้นหาไบนารี เพื่อนหลายคนต้องติดตามการค้นหาการค้นหาแบบไบนารีอย่างเป็นระเบียบโดยไม่ต้องเรียนรู้แนวคิดของการค้นหาแบบไบนารีซึ่งจะนำไปสู่การคิดเกี่ยวกับค่าขั้นต่ำการค้นหาแบบวงกลมเท่านั้น
เพื่อนหลายคนออกแถลงการณ์ในระหว่างการสัมภาษณ์ว่าระบบนิเวศดั้งเดิมของ Android โดยทั่วไปห่อหุ้มอัลกอริทึมทั่วไปและประท้วงกับอัลกอริทึมที่ไม่มีประสิทธิภาพเหล่านี้ในการสัมภาษณ์ นี่มันค่อนข้างโง่จริงๆ เราไม่พยายามที่จะใช้อัลกอริทึมการท่องจำ แต่เราพยายามที่จะเรียนรู้ความคิดที่ฉลาดในนั้น โดยการพัฒนาความสามารถในการคิดอย่างต่อเนื่องเท่านั้นที่จะช่วยให้เราได้รับการพัฒนาอาชีพที่ดีขึ้น
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น