给定一个排好升序的数组A[1]、A[2]、……、A[n]，其_阿里巴巴笔试题

推荐

月黑风高

解析：首先分析一下这个数组，假设其中某个位置的A[i] = i，那么可以肯定的值，之前的A[x] > x，之后的A[x] < x。还有一个显而易见的性质就是中间的A[i]=i一定是连续存在的，不可能跨区域存在，因为这个数组是升序的。

我给出的方法是二分查找，具体的做法是：我们假设一个新数组B，其元素是A[i] - i的值，这样的话，B[i] = 0的时候A[i] = i，而且把B数组划分成了三个部分，左边的小于零的区域，中间的等于零的区域，右边的大于零的区域。

我第一次的想法是：二分搜索这个想象中的新数组，找到值为零的下标，但是这个下标不一定是最左边的满足条件的下标，所以我们还需要写一个while来往左移动这个下标，直到找到最左边的符合条件的下标，如下代码（假设已经通过二分查找找到了符合条件的一个下标idx）：

while(A[idx-1] == (idx-1))
     idx--;

这样的话其时间复杂度就是O(logn) + O(n)，还是属于On)的范畴。

后来我想到，为什么只去随机命中一个目标下标呢！如果二分查找这个数据的边界的话，就能直接得到最左边符合条件的下标了！其实二分查找不仅仅适用于对一个元素的搜索，也可以用于两个、三个特定相对位置元素的搜索。每次查找的时候，假设当前位置是mid，那么只要判断当前A[mid] - mid是否小于零，以及后一个元素A[mid+1] - (mid+1) == 0就行了。

#include  <iostream>  
using namespace std;  
  
int BinarySearch(int cc[], int len)  
{  
   int l = 0, r = len, mid;  
   while (l <= r)  
   {  
      mid = l + ((r-l) >> 1);  
      if(mid == 0 && cc[mid] == mid)   // 若数组一开始就符合条件  
         return 0;  
      // 若满足条件的下标不是从0开始，则边界是前一个<0，且后一个=0  
      if (cc[mid]-mid < 0 && cc[mid+1]-(mid+1) == 0)  
         return mid+1;  
      // 二分查找边界：前一个<0，且后一个=0  
      if (cc[mid] - mid >= 0)  
         r = mid-1;  
      else  
         l = mid+1;  
   }  
   return -1;  
}  
  
int main()  
{  
   // int cc[] = {0, 1};  
   // int cc[] = {0, 1, 2, 3, 4, 5, 6, 7};  
   // int cc[] = {-9, -8, -4, -2, 4, 5, 9};  
   // int cc[] = {-5, -4, -3, 5, 6, 7};  
   int len = sizeof(cc)/sizeof(int);  
   int idx = BinarySearch(cc, len);  
   if(idx != -1)  
   {  
      while(cc[idx] == idx)  
      {  
         printf("%d ", idx);  
         idx++;  
      }  
   }  
   else  
   {  
      printf("Not found\n");  
   }  
  
   getchar();  
   return 0;  
}

OK! 由于程序是原生的二分查找，所以时间复杂度为O(logn)，没有占用额外的空间。并且不需要区分正整数还是负整数，数据类型也可以改成double没问题。

编辑于 2015-01-06 16:14:57 回复(7)

为梦而飞

因为是升序，而且值是不存在相等的情况。所以这个时候可以考虑从相邻两个节点差值肯定>=1.（也就是A[i + 1] - A[i] >= 1）.而数组的下标，肯定相邻的差值为1. 即( i+1 - i = 1).

简而言之，令 F(i) = A(i) - i; F(i+1) > F(i)，所以这个函数是个递增的函数。

所以

1）如果某个节点 A[i] > i了。那么它后面的肯定不存在相等的情况。搜索可以减半

2）如果某个节点 A[i] < i了。那么它前面的肯定不存在相等的情况。搜索可以减半

3）如果某个节点 A[i] == i了。那么可以往两边继续找相等的情况。

那就可以利用分治思想，进行二分一般的情况O(logn); 最差情况0(n);

编辑于 2015-04-01 11:38:35 回复(6)

VDreamS_Right

<div> 使用二分查找法，如果A[k]<k，就在右边查找，如果A[k]>k，就在左边查找。如果A[k]=k，则以当前位置分别向左和向右判断是否A[k]=k，一定不满足，则立即停止这个方向的判断。 </div> <div> 复杂度分析： </div> <div> 最好情况下O(log(n))，最坏情况下O(n)。 </div>

发表于 2015-08-21 11:47:55 回复(0)

牛客791082号

数据类型改成double是不行的！

发表于 2015-07-01 14:36:58 回复(0)

小暖壶

解题时需要注意三点：

1.A[i]=i的位置一定是连着的，前面的是A[i]<i,后面是A[i]>i。转换成前面A[i]-i<0,A[i]-i=0,A[i]-i>0;

2.采用二分查找确定A[i]-i=0的位置

3.如何确定最左边的A[i]-i=0的位置，在进行二分查找时进行判断if(A[mid]-mid<0&&A[mid+1]-(mid+1)==0)return mid+1;

发表于 2015-03-03 11:26:11 回复(0)

gky

首先假设数组的值都为非负整数

int cnt = 0;

for (int i = 1; i <= n; i++) {

if (i == A[i])

cnt++;

else

i = A[i];

}

cnt的值即为A[i]=i的个数，如果需要所有的下标，可以用一个vector单独保存一下

最坏的时间复杂度为O(n)

发表于 2014-12-10 20:41:09 回复(3)

shuiqi

public static List getNumber(int[] n){

int length = n.length;

List<Integer> resultArray = new ArrayList<Integer>();

for(int i = 0;i < length;i++){

if(i == n[i]){

resultArray.add(i);

}

return resultArray;

}

时间复杂度：

由于是从0~n遍历一遍，所以时间复杂度是O（n）

空间复杂度：

由于满足条件的下标数目不确定，申请了一个list用来存储满足条件的下标。空间复杂度是O（n）

发表于 2016-09-06 10:20:23 回复(0)

SamStevent

数组分析：因为数组是递增的，而且值不重复，所以步距>=1，而数组下标则是步距=1的一个数组，也就是说A[s]-A[s-i]>=i（i>=0）可推出 A[s+i]>=A[s]+i和A[s-i]<=A[s]-i 。当A[s]<s时，若x<s，则A[x]<=A[s]-(s-x)<s-(s-x)<x ；当A[t]>t时，若x>t，则A[x]>=A[t]+(x-t)>t+(x-t)>x ；当s<t,且A[s]=s,A[t]=t时，若s<=x<=t，则A[x]<=A[t]-(t-x)<=t-(t-x)<=x，A[x]>=A[s]+(x-s)>=s+(x-s)>=x，所以A[x]=x。

解决方案：根据上述的分析可知我们只要找到第一个令A[s]=s的元素和最后一个另A[t]=t的元素，则小于s部分均有A[x]<x ，大于t部分均有A[x]>x ，处于s、t之间的均有A[x]=x。由于数组由x<s，s<=x<=t，t<x三个连续的片段组成，所以我们可以用二分法的方法找s和t，其时间复杂度均为o(logn) ，所以解决这个问题的时间复杂度为O(logn)。

发表于 2016-04-19 17:02:15 回复(0)

起名废23333

马住

发表于 2016-03-08 21:35:53 回复(0)

imba

这题出自哪呀。怎么找

发表于 2015-11-06 00:38:11 回复(0)

脑脑

typedef double ElemType;
void find(ElemType *arr,int left,int right )
{
	if(right<left||arr==NULL)//当右下标小于左下标，函数返回。
		return;
	if(arr[right]<left||arr[left]>right)
		//当数组最后一个值小于左下标
			//或者数组最后一个值大于右下标。
				//函数返回。
		return ;
	int med=(left+right)/2;
	if(arr[med]==med)
		cout<<med<<" ";
	find(arr,left,med-1);//递归左边区域
	find(arr,med+1,right);//递归右边区域
}
谁指点下啊

发表于 2015-08-22 17:04:46 回复(0)

月夜星空

<div> O(logn)折半查找的方法； </div> <div> 由于要找到A[i] = i;显然数组是整形的； </div> <div> 也就是找到A[i]-i = 0;的所有i； </div> <div> int findEqual(int A[],int length) </div> <div> { </div> <div>     if(length<=0)<br /> </div> <div>          return -1; </div> <div>     int low = 0;high = length-1; </div> <div>     int mid; </div> <div>     while(low<high) </div> <div>     { </div> <div>         mid = (low+high)>>1; </div> <div>         if(A[mid]-mid==0)<br /> </div> <div>         {<br /> </div> <div>             print(A,mid,length);<br /> </div> <div>             break;<br /> </div> <div>         }<br /> </div> <div>         else<br /> </div> <div>             if(A[mid]>mid)<br /> </div> <div>                   high = mid;<br /> </div> <div>             else<br /> </div> <div>                   low = mid;<br /> </div> <div>     }        </div> <div> } </div> <div> void print(int A[],int mid,int length) </div> <div> { </div> <div>     int temp = mid-1;<br /> </div> <div>     while(A[temp]-temp==0)<br /> </div> <div>         cout<<temp--<<"  ";<br /> </div> <div>     cout<<mid<<"  "; </div> <div>     temp = mid+1; </div> <div>     while(A[temp]-temp==0) </div> <div>         cout<<temp++<<"  "; </div> <div>     cout<<endl;<br /> </div> <div> } </div> <div> <br /> </div>

发表于 2015-08-22 12:02:02 回复(0)

DCBA

<pre class="prettyprint lang-cpp">/************************************************************************* * ---------> File Name: search.c * ---------> Author: ChengfeiZH * ---------> Mail: chengfeizh@gmail.com * ---------> Time: 2015年08月20日星期四 11时11分07秒 ************************************************************************/ #include <stdio.h> void search(char *a, int low, int high) { int mid; if(low <= high) { mid = (low + high) / 2; if (a[mid] < mid) { search(a, low, a[mid] - 1); search(a, mid + 1, high); } else if (a[mid] > mid) { search(a, a[mid] + 1, high); search(a, low, mid - 1); } else { if (low <= high){ printf("%d ", mid); search(a, low, mid - 1); search(a, mid + 1, high); } } } } int main() { // char a[10] = {0, 1}; // search(a, 0, 2 - 1); char b[10] = {0, 3, 3, 3, 5, 5, 6}; search(b, 0, 7 - 1); return 0; } </pre> <br />

发表于 2015-08-21 08:18:27 回复(0)

牛客492036号

#include <iostream>
#include <vector>
using namespace std;

void search1(int *a, vector<int> &r, int begin, int end)
{
int i = begin;
int j = end;
if (i > j)
  return;

  int mid = (i + j) / 2;
  if (a[mid] == mid)
  {
   r.push_back(mid);
   search1(a, r, i, mid - 1);
   search1(a, r, mid + 1, j);
  }
  else if (a[mid] < mid)
   search1(a, r, mid + 1, j);
  else if (a[mid]>mid)
   search1(a, r, i, mid - 1);

}
vector<int> search(int *a, int begin, int end)
{
vector<int> re;
search1(a, re, begin, end);
return re;
}

int main()
{
 int a[] = { -1, 0, 1, 3, 4, 6, 8 };
 int n = sizeof(a) / sizeof(int);
 vector<int> res;
 res = search(a, 0, n - 1);
 for (int i = 0; i < res.size(); i++)
  cout << res[i] << "   ";
 cout << endl;
 return 0;
}

发表于 2015-08-19 21:00:39 回复(0)

天空中的云彩

<pre class="prettyprint lang-java">面试金典里有一道类似的题：根据数组有序知，利用二分查找思想：<span></span></pre> <div> public static int magic(int[] array,int start,int end){ </div> <div>     if(end<start||start<0||end>=array.length){ </div> <div>         return -1; </div> <div> <span></span>    }<br /> </div> <div> <br /> </div> <div>     int mid=(start+end)/2;<br /> </div> <div>     if(array[mid]==mid){ </div> <div>         return mid; </div> <div>     }else if(array[mid]<mid){ </div> <div>         //若是数组的值小于索引值，则必定在右边<br /> </div> <div>         return magic(array,mid+1,end);<br /> </div> <div>     }else{ </div> <div>         return magic(array,start,mid-1);<br /> </div> <div>     }<br /> </div> <div> } </div> <div> <br /> </div> <div> <br /> </div> <div> --------------------------------------------------------------- </div> <div> 若数组中有重复元素，左右部分都得搜索，但可以跳过一些元素 </div> <div> 一般模式：先比较midIndex和midValue是否相同，若两者不同，则按如下方式递归搜索左半部分和右半部分 </div> <div> 左半部分：搜索索引从start到Math.min(minIndex-1,midValue); </div> <div> 右半部分：搜索索引从Math.max(midIndex+1,minValue); </div> <div> public static int magicFast(int[] array,int start,int end){ </div> <div>     if(end<start||start<0||end>=array.length){ </div> <div>         return -1; </div> <div>     } </div> <div>     int midIndex=(start+end)/2;<br /> </div> <div>     int midValue=array[midIndex];<br /> </div> <div>     if(midValue==midIndex){ </div> <div>         return midIndex;<br /> </div> <div>     }<br /> </div> <div> <br /> </div> <div>     /*搜索左半部分*/<br /> </div> <div>     int leftIndex=Math.min(midIndex-1,midValue);<br /> </div> <div>     int left=magicFast(array,start,leftIndex);<br /> </div> <div>     if(left<=0){ </div> <div>         return left;<br /> </div> <div>     }<br /> </div> <div>     <br /> </div> <div>     /*搜索右半部分*/<br /> </div> <div>     int rightIndex=Math.max(midIndex+1,midValue);<br /> </div> <div>     int right=magicFast(array,righIndex,end);<br /> </div> <div>     <br /> </div> <div>     return right;<br /> </div> <div> } </div> <div> <br /> </div> <div> public static int magicFast(int[] array){ </div> <div>     return magicFast(array,0,array.length-1);<br /> </div> <div> } </div>

发表于 2015-08-13 11:25:04 回复(0)

早上的星星

int * isEqual(int *A)

{

int *result = null;

for(int i = 1; i<=n; i++)

{

if(a[i] == i)

{

result = i;

result++;

}

return result;

}

//时间复杂度为O(n)

发表于 2015-08-01 21:08:48 回复(0)

洋子

#include <iostream>
using namespace std;
int binarysearch(int *x,int key, int begin, int end)
{
  if(begin>end)
  {
   return -1;
  }
  int mid=(begin+end)/2;
  if(key==x[mid])
  {
   return mid;
  }
  else if(key<x[mid])
  {
   return binarysearch(x,key,begin,mid-1);
  }
  else
  {
   return binarysearch(x,key,mid+1,end);
  }
}
int main()

{

int a[n]= {A[1],A[2],……,A[n]};
int b[n];
int i;
for(i=0;i<n;i++)
{
 b[i]=a[i]-i;
}
int m = binarysearch(b,0,0,sizeof(b)/sizeof(int)-1);

cout << m << endl;

return 0;

}
算法复杂度为：O(log(n));

发表于 2015-05-14 16:54:47 回复(0)

一鸣惊人

void select(array,n)

{ int j=0;

int a[n];

length=strlen(array);

for(i=1;i<=length;i++)

{ if(array[i]==i) a[j]=i;

j++;

}

return 1;

}

复杂度为O(n)

发表于 2015-04-07 15:33:42 回复(0)

『道』

发表于 2015-04-04 10:05:01 回复(0)

cc-xx

public class CountSame {

static int cont;

public static void main(String[] args) {
float[] test = {0,1,1.2f,1.3f,4,4.5f,5.6f,7,7.1f,9};
count(test, 0, 9);
System.out.println(cont);
}
public static void count(float[] t,int left,int right){
int center = (left+right)/2;
if(left<=right)
if(t[center] >= center ){
if(t[center] == center) cont++;
count(t, left, center-1);
count(t, center+1, right);
}else if(t[center] < center){
count(t,center+1,right);
}
}
}

发表于 2015-03-30 20:43:06 回复(0)

Manfestain

采用树状结构的思想吧，每次处理当前的根节点
1> A[i]-i>0 向左跑
2> A[i]-i<0 向右跑
3> A[i]-i=0 就找到了
时间复杂度为O（logn）空间复杂度O(1)

发表于 2015-03-29 21:24:33 回复(0)

给定一个排好升序的数组A[1]、A[2]、……、A[n]，其

问题信息

热门推荐

相关试题