剑指offer 面试题38
2024-09-02 05:31:13
面试题38：数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1，2，3，3，3，3，4，5}和数字3，由于3在这个数组中出现了4次，因此输出4。
主要的思路是进行二分搜索找到第一个位置和最后一个位置，一开始的代码如下
#include <cstdio>
#include <cstdlib> int num[];
int n; int getFirstk(int from, int to, int k) {
if(to < from) {
return -;
} int mid = (from+to)/;
if(num[mid] < k) {
return getFirstk(mid+,to,k);
}
else if(num[mid] > k) {
return getFirstk(from,mid-,k);
}
else {
if(mid == ) {
return ;
}
if(num[mid-] == k) {
return getFirstk(from,mid-,k);
}
else if(num[mid-] != k) {
return mid;
}
}
} int getLastK(int from, int to, int k) {
if(to < from) {
return -;
} int mid = (from+to)/;
if(num[mid] < k) {
return getLastK(mid+,to,k);
}
else if(num[mid] > k) {
return getLastK(from, mid-, k);
}
else {
if(mid == n-) {
return mid;
}
else {
if(num[mid+] == k) {
return getLastK(mid+,to,k);
}
else {
return mid;
}
}
}
} int main(int argc, char const *argv[])
{ while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&num[i]);
}
int k;
scanf("%d",&k);
int from = getFirstk(,n-,k);
int to = getLastK(,n-,k);
int ans; ans = to - from+; printf("%d\n",ans);
}
return ;
}
这段代码的主要问题在于没有考虑元素没有找到的情况，倘若都没找到，from和to都为-1，则会导致结果为1
修改如下
#include <cstdio>
#include <cstdlib> int num[];
int n; int getFirstk(int from, int to, int k) {
if(to < from) {
return -;
} int mid = (from+to)/;
if(num[mid] < k) {
return getFirstk(mid+,to,k);
}
else if(num[mid] > k) {
return getFirstk(from,mid-,k);
}
else {
if(mid == ) {
return ;
}
if(num[mid-] == k) {
return getFirstk(from,mid-,k);
}
else if(num[mid-] != k) {
return mid;
}
}
} int getLastK(int from, int to, int k) {
if(to < from) {
return -;
} int mid = (from+to)/;
if(num[mid] < k) {
return getLastK(mid+,to,k);
}
else if(num[mid] > k) {
return getLastK(from, mid-, k);
}
else {
if(mid == n-) {
return mid;
}
else {
if(num[mid+] == k) {
return getLastK(mid+,to,k);
}
else {
return mid;
}
}
}
} int main(int argc, char const *argv[])
{ while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&num[i]);
}
int k;
scanf("%d",&k);
int from = getFirstk(,n-,k);
int to = getLastK(,n-,k);
int ans;
if(from == - || to == -) {
ans = ;
}
else {
ans = to - from+;
}
printf("%d\n",ans);
}
return ;
}
找到一个在线测试的oj
http://www.nowcoder.com/books/coding-interviews/70610bf967994b22bb1c26f9ae901fa2?rp=2
此oj的编译条件很严格，而且形式与平常的oj略有不同，花了一点时间来适应，ac代码如下
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int n = data.size();
if(n < ) {
return ;
}
int from = getFirstk(data,,n-,k);
int to = getLastK(data,,n-,k,n);
if(from == - || to == -) {
return ;
}
int ans = to - from+;
return ans;
}
int getFirstk(const vector<int> &num,int from, int to, int k) {
if(to < from) {
return -;
}
int mid = (from+to)/;
if(num[mid] < k) {
return getFirstk(num,mid+,to,k);
}
else if(num[mid] > k) {
return getFirstk(num,from,mid-,k);
}
else {
if(mid == ) {
return ;
}
if(num[mid-] == k) {
return getFirstk(num,from,mid-,k);
}
else if(num[mid-] != k) {
return mid;
}
}
return -;
}
int getLastK(const vector<int> &num,int from, int to, int k, int n) {
if(to < from) {
return -;
}
int mid = (from+to)/;
if(num[mid] < k) {
return getLastK(num,mid+,to,k,n);
}
else if(num[mid] > k) {
return getLastK(num,from, mid-, k,n);
}
else {
if(mid == n-) {
return mid;
}
else {
if(num[mid+] == k) {
return getLastK(num,mid+,to,k,n);
}
else {
return mid;
}
}
}
return -;
}
};
最新文章
- MahApps.Metro使用
- QImage：：drawRect 和 fillRect在处理大面积区域时代价高昂
- CF459E Pashmak and Graph （DP？
- Svn版本控制工具的作用和应用
- 一个简单的CORBA例子
- 1.Java为什么能跨平台运行？请简述原理。
- Logspout安装、使用
- python学习笔记之初识Python
- Struts2 教程
- js 保留小数位数
- 转：CFile::Seek
- [Ext JS 4] 布局之实战一 - 中间区块不会自动伸展 （tab）
- 修改es最大返回结果数
- Scala 安装 Exception in thread "main" java.lang.VerifyError: Uninitialized object exists on backward branch 96
- linux iio子系统
- JavaScript复制文本探究
- 第n次搭建 SSM 框架
- 微软官方的.net开发人员代码示例
- mac mysql5.5升级5.7记录
- Spring boot --- Spring Oauth(三)