//数字在排序数组中出现的次数
#include &iostream&
int GetFirstK(const int* data,int length,int k,int start,int end);
int GetLastK(const int* data,int length,int k,int start,int end);
int GetNumberOfK(int* data,int length,int k)
int number = 0;
if(data!=nullptr&&length&0)
int first = GetFirstK(data,length,k,0,length-1);
int last = GetLastK(data,length,k,0,length-1);
if(last&-1&&first&-1)
number =last - first+1;
int GetFirstK(const int* data,int length,int k,int start,int end)
if(start&end)
return -1;
int middleIndex = (start+end)/2;
int middleData = data[middleIndex];
if(middleData==k)
if((middleIndex&0&&data[middleIndex-1]!=k)||middleIndex==0)
return middleI
end = middleIndex-1;
else if(middleData&k)
end = middleIndex-1;
start = middleIndex+1;
return GetFirstK(data,length,k,start,end);
int GetLastK(const int* data,int length,int k,int start,int end)
if(start&end)
return -1;
int middleIndex = (start+end)/2;
int middleData = data[middleIndex];
if(middleData==k)
if((middleIndex&length-1 && data[middleIndex+1]!=k)||middleIndex ==length-1)
return middleI
start = middleIndex+1;
else if(middleData&k)
end = middleIndex-1;
start = middleIndex+1;
return GetLastK(data,length,k,start,end);
// ====================测试代码====================
void Test(const char* testName, int data[], int length, int k, int expected)
if(testName != nullptr)
printf(&%s begins: &, testName);
int result = GetNumberOfK(data, length, k);
if(result == expected)
printf(&Passed.\n&);
printf(&Failed.\n&);
// 查找的数字出现在数组的中间
void Test1()
int data[] = {1, 2, 3, 3, 3, 3, 4, 5};
Test(&Test1&, data, sizeof(data) / sizeof(int), 3, 4);
// 查找的数组出现在数组的开头
void Test2()
int data[] = {3, 3, 3, 3, 4, 5};
Test(&Test2&, data, sizeof(data) / sizeof(int), 3, 4);
// 查找的数组出现在数组的结尾
void Test3()
int data[] = {1, 2, 3, 3, 3, 3};
Test(&Test3&, data, sizeof(data) / sizeof(int), 3, 4);
// 查找的数字不存在
void Test4()
int data[] = {1, 3, 3, 3, 3, 4, 5};
Test(&Test4&, data, sizeof(data) / sizeof(int), 2, 0);
// 查找的数字比第一个数字还小，不存在
void Test5()
int data[] = {1, 3, 3, 3, 3, 4, 5};
Test(&Test5&, data, sizeof(data) / sizeof(int), 0, 0);
// 查找的数字比最后一个数字还大，不存在
void Test6()
int data[] = {1, 3, 3, 3, 3, 4, 5};
Test(&Test6&, data, sizeof(data) / sizeof(int), 6, 0);
// 数组中的数字从头到尾都是查找的数字
void Test7()
int data[] = {3, 3, 3, 3};
Test(&Test7&, data, sizeof(data) / sizeof(int), 3, 4);
// 数组中的数字从头到尾只有一个重复的数字，不是查找的数字
void Test8()
int data[] = {3, 3, 3, 3};
Test(&Test8&, data, sizeof(data) / sizeof(int), 4, 0);
// 数组中只有一个数字，是查找的数字
void Test9()
int data[] = {3};
Test(&Test9&, data, sizeof(data) / sizeof(int), 3, 1);
// 数组中只有一个数字，不是查找的数字
void Test10()
int data[] = {3};
Test(&Test10&, data, sizeof(data) / sizeof(int), 4, 0);
// 鲁棒性测试，数组空指针
void Test11()
Test(&Test11&, nullptr, 0, 0, 0);
int main(int argc, char* argv[])
数字在排序数组中出现的次数
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3909次
排名：千里之外
原创：28篇
(5)(2)(1)(1)(16)(1)(2)14.输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)
时间： 12:24:00
&&&& 阅读：611
&&&& 评论：
&&&& 收藏：0
标签：待完善！
转载请注明出处：&
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
我觉得输出下标更为合理
借鉴快速排序的思想：
（1）让指针指向数组的头部和尾部，相加，如果小于M，则增大头指针，如果大于则减小尾指针
（2）退出的条件，相等或者头部=尾部
java实现源码：
1 package com.
3 import java.util.HashM
* 题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，
使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。
* @author wjh
10 public class _14AscSortSum {
* @param args
public static void main(String[] args) {
_14AscSortSum sum = new _14AscSortSum();
int[] a = {-3,-2,0,1,2,3,6,7,9,15,17,19};
HashMap&Integer,Integer& map = new HashMap&Integer,Integer&();
map = sum.searchSum(a,9,map);
sum.printResult(a,map);
//打印查找结果
//查找 ,下标从0开始
private HashMap&Integer,Integer& searchSum(int[] a, int Num, HashMap&Integer,Integer& map){
int n = a.
int i=0,j=n-1;
//i和j分别保存当前较小的和交大的数据
//Map map = new HashMap&Integer,Integer&();
while(i&j){
//查找条件
while(i&j && (a[i]+a[j])&Num){
if(i&j&&(a[i]+a[j])==Num){
map.put(i, j);
//如果找到就结束的话加上这句
while(i&j && (a[i]+a[j])&Num){
if(i&j&&(a[i]+a[j])==Num){
map.put(i, j);
//如果找到就结束的话加上这句
//打印查找结果
private void printResult(int[] a, HashMap&Integer,Integer& map){
int n = map.size();
System.out.println("没有找到！");
System.out.println("这是找到的所有元素：");
for(Integer key: map.keySet()){
System.out.println("下标为:("+key+","+map.get(key)+"),
值为:"+a[key]+","+a[map.get(key)]);
1 package com.
3 import java.util.HashM
* 题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，
使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。
* @author wjh
10 public class _14AscSortSum {
* @param args
public static void main(String[] args) {
_14AscSortSum sum = new _14AscSortSum();
int[] a = {-3,-2,0,1,2,3,6,7,9,15,17,19};
HashMap&Integer,Integer& map = new HashMap&Integer,Integer&();
map = sum.searchSum(a,9,map);
sum.printResult(a,map);
//打印查找结果
//查找 ,下标从0开始
private HashMap&Integer,Integer& searchSum(int[] a, int Num, HashMap&Integer,Integer& map){
int n = a.
int i=0,j=n-1;
//i和j分别保存当前较小的和交大的数据
//Map map = new HashMap&Integer,Integer&();
while(i&j){
//查找条件
while(i&j && (a[i]+a[j])&Num){
if(i&j&&(a[i]+a[j])==Num){
map.put(i, j);
//如果找到就结束的话加上这句
while(i&j && (a[i]+a[j])&Num){
if(i&j&&(a[i]+a[j])==Num){
map.put(i, j);
//如果找到就结束的话加上这句
//打印查找结果
private void printResult(int[] a, HashMap&Integer,Integer& map){
int n = map.size();
System.out.println("没有找到！");
System.out.println("这是找到的所有元素：");
for(Integer key: map.keySet()){
System.out.println("下标为:("+key+","+map.get(key)+"),
值为:"+a[key]+","+a[map.get(key)]);
运行结果：
这是找到的所有元素：下标为:(2,8), 值为:0,9下标为:(4,7), 值为:2,7下标为:(5,6), 值为:3,6
&&国之画&&&& &&
版权所有 京ICP备号-2
迷上了代码！