JavaScript 数组中的四分之一元素
问题
JavaScript函数,它接收按递增顺序排序的整数数组arr。
数组中恰好有一个整数出现的次数超过四分之一(25%),我们的函数应该返回该数字。
例如,如果函数的输入是-
const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];
那么输出应该是-
const output = 7;
示例
此代码将是-
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