題目一：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)债鸡。
統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)铛纬。例如，輸入排序數(shù)組{1, 2, 3, 3, 3, 3, 4, 5}和數(shù)字3告唆，由于3在這個數(shù)組中出現(xiàn)了4次，因此輸出4模她。
練習地址
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2
https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
參考答案
public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0) {
return 0;
}
int first = getFirst(array, k, 0, array.length - 1);
int last = getLast(array, k, 0, array.length - 1);
if (first > -1 && last > -1) {
return last - first + 1;
} else {
return 0;
}
}
private int getFirst(int[] array, int k, int start, int end) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid > 0 && array[mid - 1] != k || mid == 0) {
return mid;
} else {
end = mid - 1;
}
} else if (array[mid] > k) {
end = mid - 1;
} else {
start = mid + 1;
}
return getFirst(array, k, start, end);
}
private int getLast(int[] array, int k, int start, int end) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid < array.length - 1 && array[mid + 1] != k || mid == array.length - 1) {
return mid;
} else {
start = mid + 1;
}
} else if (array[mid] > k) {
end = mid - 1;
} else {
start = mid + 1;
}
return getLast(array, k, start, end);
}
}
復雜度分析
- 時間復雜度：O(logn)侈净。
- 空間復雜度：O(logn)。
題目二：0~n-1中缺失的數(shù)字
一個長度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的元扔，并且每個數(shù)字都在范圍0 ~ n-1之內(nèi)。在范圍0 ~ n-1內(nèi)的n個數(shù)字中有且只有一個數(shù)字不在該數(shù)組中澎语，請找出這個數(shù)字验懊。
練習地址
https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
參考答案
class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (nums[mid] != mid) {
if (mid == 0 || nums[mid - 1] == mid - 1) {
return mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left == nums.length) {
return nums.length;
}
// 無效的輸入，比如數(shù)組不是按要求排序的减俏，
// 或者有數(shù)字不在 0~n-1 范圍之內(nèi)
return -1;
}
}
復雜度分析
- 時間復雜度：O(logn)歌溉。
- 空間復雜度：O(1)。
題目三：數(shù)組中數(shù)值和下標相等的元素痛垛。
假設一個單調(diào)遞增的數(shù)組里的每個元素都是整數(shù)并且是唯一的。請編程實現(xiàn)一個函數(shù)漫谷，找出數(shù)組中任意一個數(shù)值等于其下標的元素蹂析。例如，在數(shù)組{-3, -1, 1, 3, 5}中电抚，數(shù)字3和它的下標相等。
參考答案
public int getNumberSameAsIndex(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int left = 0, right = numbers.length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (numbers[mid] == mid) {
return mid;
} else if (numbers[mid] > mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
復雜度分析
- 時間復雜度：O(logn)俺祠。
- 空間復雜度：O(1)借帘。
