ปัญหา
หาตัวเลขใน sorted array ที่ปรากฏ > 25% (n/4 ครั้ง) ใช้ binary search
ตัวอย่าง
arr = [3, 5, 5, 7, 7, 7, 7, 8, 9] -> 7 (4/9 > 25%)
ตัวอย่างโค้ด
const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];
const oneFourthElement = (arr = []) => {
const len = arr.length / 4;
const search = (left, right, target, direction = 'left') => {
let index = -1;
while (left <= right) {
const middle = Math.floor(left + (right - left) / 2);
if (arr[middle] === target) {
index = middle;
if (direction === 'left') right = middle - 1;
else left = middle + 1;
} else if (arr[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return index;
};
for (let i = 1; i <= 3; i++) {
const index = Math.floor(len * i);
const num = arr[index];
const loIndex = search(0, index, num, 'left');
const hiIndex = search(index, arr.length - 1, num, 'right');
if (hiIndex - loIndex + 1 > len) {
return num;
}
}
};
console.log(oneFourthElement(arr));
ผลลัพธ์
7
คำอธิบาย
ใน sorted array ตัวเลขที่ > 25% ต้องอยู่ที่ตำแหน่ง n/4, 2n/4, 3n/4 อย่างน้อยหนึ่งตำแหน่ง
ตรวจสอบ 3 ตำแหน่งนี้: หา first/last occurrence ด้วย binary search คำนวณ frequency
Time: O(log n), Space: O(1)
LeetCode 1287 Element Appearing More Than 25% In Sorted Array
