Toy_ #18.getItemFromTwoSortedArrays
12522 ワード
-質問:
長さm,nで昇順に並べられた自然配列を入力して、すべての要素のk番目の要素を返します.
I/O例
let arr1 = [1, 4, 8, 10];
let arr2 = [2, 3, 5, 9];
let result = getItemFromTwoSortedArrays(arr1, arr2, 6);
console.log(result); // --> 8
arr1 = [1, 1, 2, 10];
arr2 = [3, 3];
result = getItemFromTwoSortedArrays(arr1, arr2, 4);
console.log(result); // --> 3
-プール:
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
// TODO: 여기에 코드를 작성합니다.
let arr1Idx = 0;
let arr2Idx = 0;
let count = 0;
let finalNum;
while (k > count) {
if (arr1[arr1Idx] < arr2[arr2Idx]) {
finalNum = arr1[arr1Idx]
arr1Idx++;
} else {
finalNum = arr2[arr2Idx]
arr2Idx++;
}
count++;
}
return finalNum
}
ただし,上記の解答式はO(K)
時間複雑度で解答したが,O(logK)
時間複雑度で解答するには이진탐색
時間複雑度で解答しなければならない.const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
let leftIdx = 0,
rightIdx = 0;
while (k > 0) {
// 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
let cnt = Math.ceil(k / 2);
let leftStep = cnt,
rightStep = cnt;
// 엣지 케이스
// 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.
if (leftIdx === arr1.length) {
rightIdx = rightIdx + k;
break;
}
if (rightIdx === arr2.length) {
leftIdx = leftIdx + k;
break;
}
// 엣지 케이스
// 현재 카운트가 남아있는 후보 요소들보다 많을 경우, leftStep(현재 할당량)을 남아있는 요소들의 개수로 바꾼다.
if (cnt > arr1.length - leftIdx) leftStep = arr1.length - leftIdx;
if (cnt > arr2.length - rightIdx) rightStep = arr2.length - rightIdx;
// 두 배열의 현재 검사 요소 위치를 비교해서, 그 값이 작은 배열은 비교한 위치 앞에 있는 요소들을 모두 후보군에서 제외시킨다.
if (arr1[leftIdx + leftStep - 1] < arr2[rightIdx + rightStep - 1]) {
leftIdx = leftIdx + leftStep;
// 처리가 끝나면 k값을 절반으로 떨어뜨린다.
k = k - leftStep;
} else {
rightIdx = rightIdx + rightStep;
k = k - rightStep;
}
}
leftMax = arr1[leftIdx - 1] || -1;
rightMax = arr2[rightIdx - 1] || -1;
return Math.max(leftMax, rightMax);
};
Reference
この問題について(Toy_ #18.getItemFromTwoSortedArrays), 我々は、より多くの情報をここで見つけました https://velog.io/@jonghwan2_y/Toy-18.getItemFromTwoSortedArraysテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol