ในช่วงไม่กี่วันที่ผ่านมาฉันกำลังมองหางานในสภาพอากาศที่เย็นสบาย 40 °ในเซี่ยงไฮ้ ฉันรู้สึกมีความสุขมาก ทุกครั้งที่ฉันสัมภาษณ์ฉันต้องนั่งที่นั่นและเหงื่อออกเป็นเวลานานก่อนที่ฉันจะกลับมาสู่ความรู้สึกของฉัน ฉันรู้สึกถึงความรักที่ลึกซึ้งของโลกสำหรับฉัน ฉันกลับไปที่หัวข้อ ในระหว่างการสัมภาษณ์ฉันพบการทดสอบเป็นลายลักษณ์อักษรหลายครั้ง มีคำถามหนึ่งข้อ เนื่องจากฉันไม่เคยพบมันในงานจริงของฉันฉันจึงให้ความสนใจกับมัน คำถามมีดังนี้:
มีอาร์เรย์: var arr = [1,2,1,3,3,2,4,4,6,3] ซึ่งเปลี่ยนเป็นการกระจายปกติโดยการประมวลผล: [1,2,3,3,6,4,3,2,1]
ฉันจะอธิบายการแจกแจงแบบปกติสั้น ๆ ในความเป็นจริงคุณสามารถเข้าใจอาร์เรย์ที่ประมวลผลได้อย่างคร่าวๆ ปลายทั้งสองมีขนาดเล็กและตรงกลางมีขนาดใหญ่ เส้นโค้งปกติที่สะท้อนในแกนพิกัดเป็นรูปนาฬิกาโดยมีปลายทั้งสองต่ำและกลางสูง สมมาตรด้านซ้ายและขวาเพราะเส้นโค้งเป็นรูประฆังดังนั้นผู้คนมักเรียกมันว่าเส้นโค้งรูปนาฬิกา
นี่เป็นคำถามสุดท้ายสำหรับการสัมภาษณ์ เมื่อฉันมาถึงที่นี่ฉันแน่นและอากาศร้อนกระหายน้ำและหิว หญิงสาวในแผนกต้อนรับดูดีมาก (หยุดพูดเรื่องไร้สาระมันเป็นเพราะอัลกอริทึมอ่อนแอ ... ) หลังจากความคิดเล็กน้อยฉันเขียนรหัสต่อไปนี้:
var arr = [1,2,1,3,3,2,4,4,6,3] ~ (ฟังก์ชั่น (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (ฟังก์ชั่น (a, b) {return ab}) // การจัดเรียงครั้งแรก if (i%2 == 0) {temp [i/2] = sortarr [i] // ใส่ตัวห้อยไว้ด้านหน้าตามลำดับของตัวเลขสม่ำเสมอ} อื่น {temp [l- (i+1)/2] = sortarr [i] // ใส่ตัวห้อยไว้ด้านหลัง สมบูรณ์แบบ}) (arr)เนื่องจากเป็นการทดสอบที่เป็นลายลักษณ์อักษรฉันได้ทำโปรแกรมในใจของฉันสักพักและรู้สึกว่าไม่มีปัญหาใหญ่และส่งกระดาษ ต่อมาผู้สัมภาษณ์ดูกระดาษทดสอบและไม่ได้พูดถึงคำถามนี้ในระหว่างการสัมภาษณ์ ดังนั้นฉันจึงรู้สึกว่าไม่มีปัญหากับวิธีนี้ดังนั้นฉันจึงไม่ได้ถามอีกครั้งในระหว่างการสัมภาษณ์ อย่างไรก็ตามระหว่างทางกลับฉันก็นึกถึงสถานการณ์เช่นนี้:
var arr = [1,2,3,4,5,6,7,7,8,9] // อาร์เรย์ที่เพิ่มขึ้นปกติ ~ (ฟังก์ชั่น (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (ฟังก์ชั่น (a, b) {return ab}) สำหรับ (; i <l; {temp [l- (i+1)/2] = sortarr [i]}} console.log (temp) // [1, 3, 5, 7, 9, 8, 6, 4, 2] ปัญหาเกิดขึ้นใช่ด้วยวิธีนี้ส่วนซ้ายและขวาของอาร์เรย์นี้ไม่สมมาตรโดยมี 9 เป็นศูนย์กลางโดยมี 1+3+5+7 = 16 ทางด้านซ้ายและ 2+4+6+8 = 20 ทางด้านขวา เห็นได้ชัดว่าด้านซ้ายมีน้ำหนักเบาและด้านขวานั้นหนักไม่ใช่การกระจายปกติแบบสม่ำเสมอ เมื่ออาเรย์เติบโตขึ้นปัญหาจะรุนแรงขึ้นเรื่อย ๆ
สายสาย - - - ฉันเป็นตาที่กำลังจะเบ่งบาน อย่าปฏิบัติต่อฉันแบบนี้ - -
ดูเหมือนว่าไม่สามารถใช้รหัสก่อนหน้าได้ดังนั้นฉันจึงสามารถคิดใหม่ได้อีกครั้ง ในความเป็นจริงแกนกลางของปัญหาคือเพื่อให้แน่ใจว่าด้านซ้ายและขวาของอาร์เรย์มีค่าเท่ากันหรือเท่ากัน ไม่ว่าจะเป็นอาร์เรย์ของตัวเลขคี่หรือตัวเลขแม้แต่อาร์เรย์สามารถแบ่งออกเป็นสองส่วน (ค่าสูงสุดของตัวเลขคี่สามารถถือได้ว่าเป็นอาร์เรย์หมายเลขสม่ำเสมอแม้ว่าจะมีค่าสูงสุดที่เหมือนกันหลายค่าก็ไม่สำคัญ หรือตามวิธีการข้างต้นเมื่อตัวห้อยอยู่ให้วางไว้ที่ด้านซ้ายและขวาเมื่อมันแปลกวางไว้ทางด้านขวา ในกระบวนการเติบโตอาร์เรย์ทางด้านซ้ายและขวาเมื่อความยาวของอาร์เรย์เท่ากันเปรียบเทียบผลรวมของด้านซ้ายและขวา เนื่องจากมันถูกจัดเรียงจากขนาดเล็กถึงใหญ่ภายใต้สถานการณ์ปกติทางด้านขวาจะมีขนาดใหญ่กว่าด้านซ้ายจากนั้นเปลี่ยนอันแรกทางด้านขวาและคนสุดท้ายทางด้านซ้ายเพื่อให้ได้จุดประสงค์ของความสมดุล รหัสมีดังนี้:
var arr = [1,2,3,4,5,6,7,7,8,9], sortarr = arr.sort (ฟังก์ชั่น (a, b) {return ab}), l = arr.length, temp_left = [], temp_right = [] การเรียงลำดับ (arr) {var i = 0 สำหรับ (; temp_left.push (eq): temp_right.unshift (eq) ถ้า (i> 1) {ถ้า (temp_left.length == temp_right.length &&! compare (temp_left, temp_right) {wrap (temp_left, temp_right) temp_left.concat (temp_right)} // ฟังก์ชั่นผลรวมอาร์เรย์ผลรวม (arr) {return eval (arr.join ("+")); } // ฟังก์ชั่นการเปรียบเทียบอาร์เรย์เปรียบเทียบ (arr1, arr2) {return sum (arr1)> = sum (arr2)} // อันสุดท้ายในการแลกเปลี่ยนด้านซ้ายกับอันแรกบนฟังก์ชั่นที่ถูกต้อง (l, r) {var m = r.shift () r.unshift (l.pop (l.pop) 8, 5, 3, 2]ด้วยวิธีนี้การกระจายปกติทั้งหมดจะมีความสม่ำเสมอมากขึ้น ทำการทดสอบอีกสองสามชุดเพื่อดูผลกระทบ:
arr = [1,333,444,555,66,7788,909] console.log (เรียงลำดับ (arr)) // [1,444,909, 7788,555,333,66] arr = [168.6,177.5,174.2,189.3,167.2,177.6,167.8,175.5] console.log (เรียงลำดับ (arr)) // [167.2,174.2,175.5,189.3,177.6,177.6,177.5,168.5
มันดูค่อนข้างดี มีบทความอื่นในเว็บไซต์เล็ก ๆ ที่คลิกเพื่อดูซึ่งเสร็จสมบูรณ์ใน C ++ อย่างไรก็ตามผลลัพธ์สุดท้ายของบทความไม่ใช่การแจกแจงแบบปกติที่เหมือนกัน แต่มันก็คล้ายกับโปรแกรมแรกของฉัน
ฉันไม่รู้เกี่ยวกับ C ++ มากนักและฉันไม่ได้เรียกใช้ผลลัพธ์หลายชุดให้ดู นักเรียนที่สนใจสามารถลองเป็นการเปรียบเทียบ
ฉันได้ทดสอบโปรแกรมทั้งหมดในบทความนี้ใน Chrome เท่านั้น หากมีปัญหาใด ๆ กับเบราว์เซอร์อื่น ๆ ฉันหวังว่าจะฝากข้อความไว้เพื่อแจ้งให้คุณทราบ ในความเป็นจริงสิ่งนี้ไม่ยาก เพียงใช้เป็นบันทึกและสามารถใช้งานได้เมื่อจำเป็น