Nos últimos dias, estou procurando um emprego no clima frio de 40 ° em Xangai. Eu me sinto tão feliz. Toda vez que entrevisto, tenho que ficar sentado e suar por muito tempo antes de poder voltar aos meus sentidos. Sinto o profundo amor do mundo por mim. Voltei ao tópico. Durante a entrevista, encontrei vários testes escritos. Há uma pergunta. Como nunca o encontrei no meu trabalho real, presto atenção a ele. A questão é a seguinte:
Existe uma matriz: var arr = [1,2,1,3,3,2,4,6,3], que é alterada para uma distribuição normal pelo processamento: [1,2,3,3,6,4,3,2,1].
Vou explicar brevemente a distribuição normal. De fato, você pode entender aproximadamente a matriz processada. As duas extremidades são pequenas e o meio é grande. A curva normal refletida no eixo da coordenada é em forma de relógio, com as duas extremidades baixas e médias. A esquerda e a direita simétricas porque suas curvas são em forma de sino, então as pessoas geralmente chamam de curvas em forma de relógio.
Esta é a última pergunta para a entrevista. Quando cheguei aqui, eu estava apertado e o tempo estava quente, com sede e com fome. A garota na recepção parecia tão boa (pare de falar bobagem, foi porque o algoritmo era fraco ...). Depois de um pouco de reflexão, escrevi o seguinte 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}) //First arrange the array from small to large to obtain [1, 1, 2, 2, 3, 3, 3, 4, 6]for (;i<l;i++){ 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 perfeito}) (arr)Como foi um teste por escrito, eu sim o programa em minha mente por um tempo e senti que não havia grande problema e entreguei o papel. Mais tarde, o entrevistador analisou o trabalho de teste e não mencionou essa pergunta durante a entrevista. Então, senti que não havia nenhum problema com esse método, então não perguntei novamente durante a entrevista. No entanto, no caminho de volta, de repente pensei em uma situação como esta:
var arr = [1,2,3,4,5,6,7,8,9] // Uma matriz de incrementação regular ~ (function (arr) {var temp = [], i = 0, l = arr.length, sTELARR = arr.sort (function (a, b) {retorna ab}) para (; i <L; i ++) {se {temp [l- (i+1)/2] = SortARr [i]}} Console.log (temp) // [1, 3, 5, 7, 9, 8, 6, 4, 2] O problema ocorreu.Sim, dessa maneira, as partes esquerda e direita desta matriz não são simétricas, com 9 como centro, com 1+3+5+7 = 16 à esquerda e 2+4+6+8 = 20 à direita. É óbvio que a esquerda é leve e a direita é pesada, não uma distribuição normal uniforme. À medida que a matriz cresce, os problemas se tornarão cada vez mais sérios.
Linhas tiras. . . . Eu sou um botão que está prestes a florescer. Não me trate assim. . .
Parece que o código anterior não pode ser usado, então só posso repensar a solução. De fato, o núcleo do problema é garantir que os lados esquerdo e direito da matriz sejam iguais ou aproximadamente iguais. Seja uma matriz de números ímpares ou números uniformes, a matriz pode ser dividida em duas partes (o valor máximo de números ímpares também pode ser considerado uma matriz de números uniformes. Mesmo se houver vários valores máximos idênticos, não importa. Depois de classificar de pequeno a grande, ele só precisa remover o último). Ou, de acordo com o método acima, quando o subscrito estiver par, coloque -o no lado esquerdo e direito quando for estranho, coloque -o no lado direito. No processo de crescimento da matriz no lado esquerdo e direito, quando os comprimentos da matriz são iguais, compare a soma dos lados esquerdo e direito. Como é organizado de pequenas a grandes e em circunstâncias normais, o lado direito será maior que o lado esquerdo e depois trocará o primeiro na direita e o último no lado esquerdo para alcançar o objetivo do equilíbrio. O código é o seguinte:
var arr = [1,2,3,4,5,6,7,8,9], STELARR = arr.sort (função (a, b) {return ab}), l = arr.length, temp_left = [], temp_right = [] Sort (arr) {var i = 0 para (; i <; i ++) {var eq = smnd = smnd = [var i = 0 para (i <; i ++) {] 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_lright) // quando o parto é igual e o prato é igual e o parto e o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que você está fazendo com o número de, com o objetivo de avaliar que é o mesmo setor que é o que você está fazendo, com o número de pontos de idade temp_left.concat (temp_right)} // soma da soma da matriz soma (arr) {return avali (arr.join ("+")); } // Função de comparação de matriz Compare (arr1, arr2) {return sum (arr1)> = sum (arr2)} // o último nas trocas esquerda com o primeiro na função direita (l, r) {var m = r.shift () r.unshift (l.pop ()) l.push (m)} 8, 5, 3, 2]Dessa forma, toda a distribuição normal será muito mais uniforme. Faça mais alguns conjuntos de testes para ver o efeito:
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)) //[167.2,174.2,175.5,189.3,177.6,177.5,168.6,167.8]
Parece muito bom. Há outro artigo no pequeno site que clicou para visualizar, que foi concluído no C ++. No entanto, o resultado final do artigo não foi uma distribuição normal uniforme, mas foi semelhante ao meu primeiro programa.
Não sei muito sobre C ++ e não executei vários conjuntos de resultados para ver. Os alunos interessados podem experimentá -lo como uma comparação.
Eu só testei todos os programas deste artigo no Chrome. Se houver algum problema com outros navegadores, espero deixar uma mensagem para informá -lo. De fato, isso não é difícil. Basta usá -lo como um registro e pode ser usado quando necessário.