Javascript 알고리즘 질문: Combination_javascript 기술에서 1부터 9까지 반복되지 않는 N자리 숫자의 시퀀스 번호를 찾으세요.

구체적인 질문은 다음과 같습니다.

1~9 사이에서 N개의 숫자를 선택하여 반복되지 않는 N개의 숫자를 구성하고, 이를 작은 것부터 큰 것까지 번호를 매기고, 숫자 M 중 하나를 입력하면

의 숫자와 일치하는 숫자를 찾을 수 있습니다. 예를 들어 N=3, M=213입니다. 출력: [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)]--->X =2

질문을 보고 가장 먼저 생각난 것은 가장 작은 것부터 가장 큰 것까지 완전히 배열된 배열을 생성한 다음 배열을 순회하여 해당 일련 번호(배열 첨자 + 1)를 얻는 것이었습니다. 가장 작은 것부터 가장 큰 것까지 각각 생각하여 배열에 푸시를 생성한 다음 그 숫자가 현재 질문에 제공된 숫자인지 확인합니다. 그렇다면 필요한 시퀀스 번호는 현재 배열의 길이입니다. 이전 항목은 후속 항목을 계산하고 생성하는 데 시간을 낭비할 필요가 없다는 것입니다. 생성 자체의 복잡도는 높지 않으며, 16진수나 심지어 16진수까지 확장해서 큰 숫자를 준다면 사용하지 않는 데이터를 저장하기 위해 공간을 낭비하는 것도 좋지 않습니다. 어쩌면 생성이 필요하지 않은 다른 방법을 시도해 볼 수도 있습니다.

먼저 질문을 이상화해 보겠습니다. 숫자 N이 주어지면 M은 1부터 N까지 N개의 숫자로 구성됩니다(예: N=4이면 M은 1349가 아닌 1234개의 숫자로 구성됩니다. 다른 조합). 그 이유는 공통점을 분석하고 문제에 대한 해결책을 얻기 위해서는 조건을 단순화할 필요가 있고, 임의의 상황에서 이상적인 상황으로 전환하는 것은 어렵지 않기 때문에 이 글은 길지 않을 것이다. . 먼저 질문에 주어진 예를 분석해 보겠습니다. [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] 213은 세 번째 자리에 있고 첫 번째 숫자는 2입니다. 즉, 첫 번째 숫자가 1인 것은 모두 그 앞에 있습니다(123,132). 두 번째 숫자와 다음 숫자 13의 조합을 살펴보겠습니다. 첫 번째 문자 1은 이미 가장 작습니다. 앞에 숫자가 올 수 없으며, 세 번째 숫자 3을 볼 필요가 없습니다. 이전 숫자가 결정되면 마지막 숫자에 대한 가능성은 하나만 있기 때문입니다. 결과는 213 앞에 오는 것입니다. 2(첫 번째 숫자) 0(두 번째 숫자) 0(마지막 숫자) )=2 숫자, 즉 현재 숫자가 3번째 숫자인 것에 비해 답은 정말 이렇고, 다른 숫자를 분석해보면 그렇습니다. 동일합니다. 이것으로부터 우리는 특정 숫자가 현재 숫자보다 작을 가능성의 총 개수를 계산한 다음 1을 더하여 다음을 얻을 수 있는 함수(즉, 아래 코드의 setAll())가 필요하다는 결론을 내릴 수 있습니다. 원하는 결과를 확인하세요.

코드 복사 코드는 다음과 같습니다.

//기능: 각 비트를 가져옵니다. 다른 숫자인 경우 가능성의 총 개수는 현재 숫자보다 작습니다.
//a 현재 숫자 일련 번호(작은 것부터 큰 것까지)
/ /n 현재 숫자의 총 개수
function getAll(a,n){
var sum =1; //총 개수
for(var i=n;i>1;i--)sum =sum*i; //n개의 서로 다른 숫자를 n개의 위치에 배치할 수 있는 총 가능성 수를 계산합니다.
return sum*(a-1)/n //다음보다 작은 숫자에 대한 총 가능성 수를 계산합니다. 첫 번째 숫자가 a인 현재 숫자
}

//m 계산할 숫자 시퀀스
//a는 현재 숫자의 숫자와 그 다음 숫자의 크기 시퀀스를 저장합니다. number
// 예를 들어 213의 배열은 [2,1,1]입니다. a[0]은 2입니다. 213의 첫 번째 2가 213의 세 숫자 중 두 번째로 작은 순위이고 a[입니다. 1]은 13개 중 첫 번째 1이 13개 중 첫 번째로 작은 값이므로 1입니다.
function find(m){
m= (m "").split("") //현재 숫자를 분할합니다. 각 숫자의 계산을 용이하게 하는 배열
var a=new Array(m.length 1).join(1) .split("") //길이가 m인 배열을 빠르게 생성하고 모든 값은 다음과 같습니다. 1. a 배열의 함수 설명은 위 함수 헤더의 설명을 참조하세요.
for(var i=0;ifor(var j=i 1;jif( m[i]> m[j])a[i] ;
}
} //배열 생성
console. log("배열 a:",a);
for(i=1,sum=1;isum =getAll( a[i-1],m.length -i 1); //각 숫자와 다음 숫자의 조합이 현재 조합보다 작을 가능성의 총 개수를 계산하기 위해 루프에서 getAll을 호출합니다.
}
return m "은 " 합계에서 순위를 매깁니다. 전체 배열의 " 위치"
}
console.log(find(213)); //출력 3
console.log(find(123)) //출력 1
console .log(find(231)); //출력 4
console.log(find(312)); //출력 5
console.log(find(4321)) //출력 24
console.log(find(21)); //출력 2
console.log(find(1)) //출력 1