문제
다음과 같이 Numbers 배열의 정렬된 배열(오름차순으로 정렬됨)이 있다고 가정합니다. -
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ];
첫 번째 인수로 하나의 배열을 사용하고 두 번째 인수로 단일 정수 num을 사용하는 JavaScript 함수를 작성해야 합니다.
우리 함수는 배열 arr에 존재하는 num번째로 작은 요소를 반환해야 합니다.
예를 들어, 함수에 대한 입력이 -
인 경우const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]; const num = 5;
출력
그러면 출력은 다음과 같아야 합니다. -
const output = 11;
출력 설명:
11은 행렬에서 다섯 번째로 작은 요소입니다.
예시
이에 대한 코드는 -
const arr = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
];
const num = 5;
const kthSmallest = (arr = [], num = 1) => {
let low = arr[0][0]
let high = arr[arr.length-1][arr[0].length-1] + 1;
while (low < high) {
let mid = low + Math.floor((high-low)/2);
let count = 0;
for (let i = 0;i<arr.length;i++) {
for (let j=0;j<arr.length;j++) {
if (arr[i][j] <= mid) count++;
else break;
}
}
if (count < num) low = mid+1;
else high = mid;
}
return low
};
console.log(kthSmallest(arr, num)); 코드 설명:
여기서 아이디어는 -
정규 정렬된 2차원 배열이 있는 경우 대상을 찾기 위해 인덱스 범위를 사용합니다(예:
).low = 0, high = length-1, mid = (low+high)/2
대상이 인덱스 중간에 있는 숫자보다 크면 오른쪽 부분을 검색하고 작으면 왼쪽 부분을 검색합니다.
그러나 이 2차원 arr 정렬 배열에서는 이러한 중간 인덱스를 찾는 것이 불가능합니다. 여기서 직관은 k에 대해 테스트하기 위해 숫자 범위를 사용하는 것입니다. 우리는 첫 번째 숫자가 가장 작고 마지막 숫자가 가장 크다는 것을 알고 있습니다. 이것은 목표 숫자가 그 사이에 있어야 함을 의미합니다. 이 두 숫자를 낮음과 높음으로 사용하고 중간을 그 사이의 숫자로 설정하고 arr의 숫자 중 몇 개나 그 숫자보다 작은지 확인하고 그에 따라 낮음과 높음을 조정할 수 있습니다.
정확히 k개의 숫자를 얻으면 답을 찾았다는 것을 알 수 있습니다. 여기서 극도로 까다로운 부분은 우리가 mid를 계산하는 방법을 보면 우리가 테스트하는 숫자가 arr에 없을 수도 있다는 것입니다. 왜냐하면 결국 우리가 사용하는 숫자는 임의의 숫자이기 때문입니다.
이것을 설명하기 위해 우리는 우리 프로그램이 낮음과 높음이 거의 서로 부딪치는 단계에 있다고 상상할 필요가 있습니다. 예상보다 적은 수를 계산하면 low=mid+1을 설정합니다. 이렇게 하면 잠재적으로 mid가 1씩 증가합니다. 그리고 mid를 1씩 증가시키면 숫자가 arr에 포함되는지 확인할 수 있습니다.
출력
콘솔의 출력은 -
11