En los últimos días, estoy buscando un trabajo en el clima frío de 40 ° en Shanghai. Me siento tan feliz. Cada vez que entrevisto, tengo que sentarme allí y sudar durante mucho tiempo antes de poder volver a mis sentidos. Siento el profundo amor del mundo por mí. Regresé al tema. Durante la entrevista, encontré varias pruebas escritas. Hay una pregunta. Como nunca lo he encontrado en mi trabajo real, le presto atención. La pregunta es la siguiente:
Hay una matriz: var arr = [1,2,1,3,3,2,4,6,3], que se cambia a una distribución normal mediante el procesamiento: [1,2,3,6,6,4,3,2,1].
Explicaré brevemente la distribución normal. De hecho, puede comprender aproximadamente la matriz procesada. Los dos extremos son pequeños y el medio es grande. La curva normal reflejada en el eje de coordenada tiene forma de reloj, con ambos extremos bajos y medios. La simétrica izquierda y derecha porque sus curvas tienen forma de campana, por lo que las personas a menudo lo llaman curvas en forma de reloj.
Esta es la última pregunta para la entrevista. Cuando lo conseguí aquí, estaba apretado y el clima estaba caliente, sediento y hambre. La chica de la recepción se veía tan bien (deja de hablar tonterías, fue porque el algoritmo era débil ...). Después de pensar un poco, escribí el siguiente código:
var arr = [1,2,1,3,3,2,4,6,3] ~ (function (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (function (a, b) {return AB}) // Primero organizar la matriz de pequeña a grande a obtener [1, 1, 2, 3, 3, 3, 4, 6] para (; i < by++) if(i%2==0){ temp[i/2] = sortArr[i] // Put the subscripts in the front in the order of even numbers} else { temp[l-(i+1)/2] = sortArr[i] // Put the subscripts in the back to front in the order of odd numbers} } console.log(temp) // [1, 2, 3, 3, 6, 4, 3, 2, 1] It looks perfecto}) (arr)Como era una prueba escrita, hice el programa en mi mente por un tiempo y sentí que no había un gran problema y me entregué el papel. Más tarde, el entrevistador observó el documento de prueba y no mencionó esta pregunta durante la entrevista. Así que sentí que no había problema con este método, así que no volví a preguntar durante la entrevista. Sin embargo, en el camino de regreso, de repente pensé en una situación como esta:
var arrr = [1,2,3,4,5,6,7,8,9] // una matriz de incremento regular ~ (function (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (function (a, b) {return AB}) for (; i <l; i ++) {if (i%2 == 0) {Temp [i//2] {temp [l- (i+1)/2] = sortarr [i]}} console.log (temp) // [1, 3, 5, 7, 9, 8, 6, 4, 2] El problema ha ocurrido.Sí, de esta manera, las partes izquierda y derecha de esta matriz no son simétricas, con 9 como centro, con 1+3+5+7 = 16 en la izquierda, y 2+4+6+8 = 20 a la derecha. Es obvio que la izquierda es ligera y la derecha es pesada, no una distribución normal uniforme. A medida que la matriz crece, los problemas se volverán cada vez más serios.
Correas de líneas. . . . Soy un brote que está a punto de florecer. No me trates así. . .
Parece que el código anterior no se puede usar, por lo que solo puedo repensar la solución. De hecho, el núcleo del problema es garantizar que los lados izquierdo y derecho de la matriz sean iguales o aproximadamente iguales. Ya sea que se trate de una matriz de números impares o números pares, la matriz se puede dividir en dos partes (el valor máximo de los números impares también puede considerarse como una matriz de números uniforme. Incluso si hay múltiples valores máximos idénticos, no importa. Después de clasificar de pequeño a grande, solo necesita eliminar la última). O de acuerdo con el método anterior, cuando el subíndice sea uniforme, colóquelo en el lado izquierdo y derecho cuando sea extraño, colóquelo en el lado derecho. En el proceso de cultivo de la matriz en el lado izquierdo y derecho, cuando las longitudes de la matriz son iguales, compare la suma de los lados izquierdo y derecho. Debido a que está dispuesto de pequeñas a grandes, en circunstancias normales, el lado derecho será más grande que el lado izquierdo, y luego cambia el primero a la derecha y al último en el lado izquierdo para lograr el propósito del equilibrio. El código es el siguiente:
var arr = [1,2,3,4,5,6,7,8,9], sortarr = arr.sort (function (a, b) {return AB}), l = arr.length, temp_left = [], temp_right = [] function (arr) {var i = 0 for (; i <l; i ++) {var eqarr [i] i%2 == 0? temp_left.push (eq): temp_right.unshift (eq) if (i> 1) {if (temp_left.length == temp_right.length &&! Compare (temp_left, temp_right)) {wrap (temp_left, temp_right) // cuando el matrice es igual y el derecho y el derecho son mayores que el lado izquierdo es más grande que el lado izquierdo EXCHANGED temp_left.concat (temp_right)} // Función de suma de matriz sum (arr) {return eval (arr.Join ("+")); } // Array comparison function compare(arr1,arr2) { return sum(arr1) >= sum(arr2) } // The last one on the left exchanges with the first one on the right function wrap(l,r){ var m = r.shift() r.unshift(l.pop()) l.push(m) } console.log(sort(arr)) // Get [1, 4, 6, 7, 9, 8, 5, 3, 2]De esta manera, toda la distribución normal será mucho más uniforme. Haga algunos conjuntos más de pruebas para ver el efecto:
arr = [1,333,444,555,66,7788,909] console.log (sort (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 (sort (arr)) // bast167.2,174.2,175.5,189.3,177.6,177.5,168.6,167.8]
Se ve bastante bien. Hay otro artículo en el pequeño sitio que hizo clic para ver, que se completó en C ++. Sin embargo, el resultado final del artículo no fue una distribución normal uniforme, pero fue similar a mi primer programa.
No sé mucho sobre C ++, y no he ejecutado múltiples conjuntos de resultados para ver. Los estudiantes interesados pueden probarlo como comparación.
Solo he probado todos los programas en este artículo en Chrome. Si hay algún problema con otros navegadores, espero dejar un mensaje para informarle. De hecho, esto no es difícil. Simplemente úselo como registro y se puede usar cuando sea necesario.