题目一 数字在排序数组中出现的个数
题目描述
统计一个数字在排序数组中出现的次数。
解决思路
写两个二分查找分别找第一个和最后一个该数字，然后可直接出计算有几个该数字。时间复杂度为O(logn)。
这里使用二分查找的递归写法，形式可以写得更简洁（见书）。
当输入不符合规则返回-1。注意形参len表示原始数组的长度，在此题目中是必要的。注意特殊输入的处理。
代码
#include <iostream>
using namespace std;
int findFirstK(int* num,int len,int k,int beg,int end){
if(beg>end){
return -1;
}
int midIndex=(beg+end)/2;
int midNum=num[midIndex];
if(k<midNum){
return findFirstK(num, len, k, beg, midIndex-1);
}
else if(k>midNum){
return findFirstK(num, len, k, midIndex+1, end);
}
else{
if(midIndex==0||(midIndex>0&&num[midIndex-1]!=k)){
return midIndex;
}
else{
return findFirstK(num, len, k, beg, midIndex-1);
}
}
}
int findLastK(int*num,int len,int k,int beg,int end){
if(beg>end){
return -1;
}
int midIndex=(beg+end)/2;
int midNum=num[midIndex];
if(k<midNum){
return findLastK(num, len, k, beg, midIndex-1);
}
else if(k>midNum){
return findFirstK(num, len, k, midIndex+1, end);
}
else{
if(midIndex==len-1||(midIndex<len-1&&num[midIndex+1]!=k)){//此处需要原始数组的长度len
return midIndex;
}
else{
return findLastK(num, len, k, midIndex+1, end);
}
}
}
int getKCnt(int *num,int len,int k,int beg,int end){
if(num==nullptr||len<0){
return -1;
}
int cnt = 0;
int fistKIndex=findFirstK(num, len, k, beg, end);
int lastKIndex=findLastK(num, len, k, beg, end);
if(fistKIndex!=-1&&lastKIndex!=-1){
cnt=lastKIndex-fistKIndex+1;
}
return cnt;
}
int main(int argc, const char * argv[]) {
int num[]={1,2,3,4,4,4,5,6};
int len=sizeof(num)/sizeof(int);
int k=4;
int kCnt=getKCnt(num, len, k, 0, len-1);
cout<<"The count of K is:"<<kCnt<<endl;
return 0;
}
题目二 0-n-1中缺失的数字
题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0-n-1之内。在范围0-n-1内的n个数字中有且只有一个数字不在该数组中，找出这个数字。
解决思路
用二分查找找到数组中第一个树枝和下标不相等的下标，即是缺失数字。时间复杂度为O(logn)。
这里使用递归写法，使用循环写法形式更简洁。
相关知识
当数组不是有序时，可以利用数字0-n-1之和n*(n-1)/2减去 遍历数组得到的数组元素之和，即是缺失数字。由于遍历数组时间复杂度为O(logn),所以总时间复杂度为O(logn)。
代码
#include <iostream>
using namespace std;
int findMissNum(int* num,int beg,int end){
if(num==nullptr||end-beg<0){
return -1;
}
int midIndex=(beg+end)/2;
int midNum=num[midIndex];
if(midNum==midIndex){
return findMissNum(num, midIndex+1, end);
}
else if(midNum>midIndex){
if(midIndex==0||num[midIndex-1]==midIndex-1){//注意
return midIndex;
}
else{
return findMissNum(num, beg, midIndex-1);
}
}
else{
return -1;
}
}
int main(){
// int num[]={0,1,2,3,4,6,7};
int num[]={1};
int missNum=findMissNum(num, 0, sizeof(num)/sizeof(int)-1);
cout<<"The missing number is:"<<missNum<<endl;
return 0;
}
题目三 数组中数值和下标相等的元素
题目描述
假设一个单调递增数组里的每个元素都是整数且唯一。找出数组中任意一个数值等于其下标的元素。
解决思路
二分查找。时间复杂度为O(logn)。
关于细节很好的
这里使用循环写法。
二分查找的细节 第一个ok，第二、三个还需仔细理解。
参考链接 https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
C++代码
#include <iostream>
using namespace std;
int findK(int* num,int len){
if(num==nullptr||len<=0){
return -1;
}
int l=0;
int r=len-1;
while(l<=r){
int midIndex=(l+r)>>1;
int midNum=num[midIndex];
if(midNum==midIndex){
return midNum;
}
else if(midNum>midIndex){
r=midIndex-1;
}
else{
l=midIndex+1;
}
}
return -1;
}
int main(){
int num[]={-1,0,2,3,4,5,6};
// int num[]={0};
int K=findK(num, sizeof(num)/sizeof(int));
cout<<"One of the number which is equal to its index is:"<<K<<endl;
return 0;
}
Java代码
class Solution {
public int search(int[] nums, int target) {
if(nums==null){
return -1;
}
int l=0;
int r=nums.length-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
l=mid+1;
}
else{
r=mid-1;
}
}
return -1;
}
}