思路
本道題有好幾種解法
1.直接遍歷數組材蹬,判斷前后的值是否相同,找到元素開始位置和結束位置吝镣,時間復雜度O(n)
2.使用二分查找找到目標值赚导,在向前向后遍歷,找到所有的數赤惊,比上面略優(yōu)吼旧,時間復雜度也是O(n)
3.使用二分查找分別找到第一個目標值出現(xiàn)的位置和最后一個位置,時間復雜度O(logn)
在排序數組中找元素未舟,首先考慮使用二分查找
下面是使用二分查找在數組中尋找某個數
function binarySearch(data, arr, start, end) {
if (start > end) {
return -1;
}
var mid = Math.floor((end + start) / 2);
if (data == arr[mid]) {
return mid;
} else if (data < arr[mid]) {
return binarySearch(data, arr, start, mid - 1);
} else {
return binarySearch(data, arr, mid + 1, end);
}
}
找到第一次和最后一次出現(xiàn)的位置我們只需要對上面的代碼進行稍加的變形
第一次位置:找到目標值圈暗,并且前一位的數字和當前值不相等
最后一次位置:找到目標值,并且后一位的數字和當前值不相等
function GetNumberOfK(data, k) {
if (data && data.length > 0 && k != null) {
const firstIndex = getFirstK(data, 0, data.length - 1, k);
const lastIndex = getLastK(data, 0, data.length - 1, k);
if (firstIndex != -1 && lastIndex != -1) {
return lastIndex - firstIndex + 1;
}
}
return 0;
}
function getFirstK(data, first, last, k) {
if (first > last) {
return -1;
}
const mid = parseInt((first + last) / 2);
if (data[mid] === k) {
if (data[mid - 1] != k) {
return mid;
} else {
return getFirstK(data, first, mid-1, k);
}
} else if (data[mid] > k) {
return getFirstK(data, first, mid - 1, k);
} else if (data[mid] < k) {
return getFirstK(data, mid + 1, last, k);
}
}
function getLastK(data, first, last, k) {
if (first > last) {
return -1;
}
const mid = parseInt((first + last) / 2);
if (data[mid] === k) {
if (data[mid + 1] != k) {
return mid;
} else {
return getLastK(data, mid + 1, last, k);
}
} else if (data[mid] > k) {
return getLastK(data, first, mid - 1, k);
} else if (data[mid] < k) {
return getLastK(data, mid + 1, last, k);
}
}