[问答题]
因为是升序，而且值是不存在相等的情况。所以这个时候可以考虑从相邻两个节点差值肯定>=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)
<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)
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)
数组分析：因为数组是递增的，而且值不重复，所以步距>=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)
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)
<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)
#include <iostream>
#include <vector>
using namespace std;
#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 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)
#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)
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);
}
}
}
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)
采用树状结构的思想吧，每次处理当前的根节点
1> A[i]-i>0 向左跑
2> A[i]-i<0 向右跑
3> A[i]-i=0 就找到了
时间复杂度为O（logn）空间复杂度O(1)
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)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
解析：首先分析一下这个数组，假设其中某个位置的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没问题。