18个答案 按时间排序 按投票排序

0 0

采纳的答案

1，这个题目中，数组A[i]应该是个整数数组
2，由升序+两两不等可知，A[i]是个递增的数列

把A[i]连成一条线，则与直线y=x只有一个交点（或者有仅有一段重合），即满足：

如果A[i]>i，则点A[i]在直线y=x的上半部，即 对任意j>i,都有A[j]>j，i以后的区间可以抛弃；

如果A[i]<i，则点A[i]在直线y=x的下半部，即 对任意j<i,都有A[j]<j，i以前的区间可以抛弃；

这篇博客恰好是这个问题的完美解法：http://openmind.iteye.com/blog/1320859

2013年9月23日 20:33

OpenMind
704
0 1 13

• 4条评论

0 0

二分法可以的啊，Arrays.sort....
就算Double也可以调用doubleToLongBits去处理的。

2013年9月25日 13:26

unique.wu
0
0 0 0

• 添加评论

0 0

一直波动如何是好？

2013年9月25日 09:14

非法用户
14
0 0 7

• 添加评论

0 0

就是二分递归吧

2013年9月25日 00:50

sun1752709589
26
0 0 3

• 添加评论

0 0

public static int[] extract(int[] digs){
		
		if(digs == null || digs.length <= 0){
			return digs;
		}
		
		List<Integer> result = new ArrayList<Integer>();
		for ( int i = 0, n = digs.length; i < n; i++){
			if( i == digs[i]){
				result.add(i);
			}else{
				i = digs[i];
			}
		}
		
		return ArrayUtils.toPrimitive(result.toArray(new Integer[]{}));
	}

2013年9月24日 19:06

gwinthis
4
0 0 1

• 3条评论

0 0

public static int[] extract(int[] digs){

if(digs == null || digs.length <= 0){
return digs;
}

List<Integer> result = new ArrayList<Integer>();
for ( int i = 0, n = digs.length; i < n; i++){
if( i == digs[i]){
result.add(i);
}else{
i = digs[i];
}
}

return ArrayUtils.toPrimitive(result.toArray(new Integer[]{}));
}

2013年9月24日 19:06

gwinthis
4
0 0 1

• 添加评论

0 0

1. A{1] > 1 全部不相等 不用比较
2. A[n] < n 全部不相等 不用比较

在A[1] A[n] 除了1 2 的情况外：

3.A[n/2] <  n/2  A[1]-A[n/2] 不需要比较 因为不满足
4.A[n/2] >  n/2  A[n/2] - A[n] 不需要比较 因为不满足

如此下去就行了 ，二分法 妥妥的

2013年9月24日 12:55

it_like
0
0 0 3

• 2条评论

0 0

这道题题目并没有说数组元素的是否为整数，是否可以为负数。

最坏的假设，假设数组元素为小数可以为负数。那么只能通过遍历来查找。

稍微好点的假设，假设数组元素为整数可以为负数。那么通过两次二分查找，找到解段的开始位置和结束位置。

最好的假设，假设数组元素为整数且不能为负数。那么通过一次二分查找，找到解段的结束位置，开始位置必定是第一个数组元素（或者无解）。

2013年9月24日 00:12

iceofst
0
0 0 1

• 添加评论

0 0

之前对题目加了个整形约束，下面是我对非整形情况的处理，思路还是尽可能的丢弃不可能的区间：
假如给定任意区间A[i]至A[j]，判断其内部是否可能有符合的元素，提出以下论点：
1，j-(i+1)必须大于等于1，即i至j中间还有元素
2，A[j-1]的整数部分-A[i]的整数部分必须大于等于1
3，A[i]的整数部分必须小于j-1
4，A[j]的整数部分必须大于i+1
以上论点也是比较容易证明的
函数check（index）：判断A[index]是否是符合的元素
函数subFind(int first, int last)：判断first至last中是否可能有符合的元素，如果有缩小范围计算，即选取first和last之间任意一点i，判断first+1至i区间是否符合元素；以及i+1至last-1之间是否有符合的元素，依次递进。

下面给一段代码：
其中，由于java数组是从0开始的，加了偏移量；选取点的策略使用了中值法（可以有其他选择）；

public class FindTester {

	//static double[] a = { -0.9, -0.6, 0, 0.2, 0.3, 6, 
	//	6.1, 6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 11, 11.1, 11.2, 14 };

	static double[] a = { -0.9, -0.6, 0, 0.2, 0.3, 6, 
		6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14 };
	
	public static void main(String[] args) {
		subFind(0, a.length-1);
	}

	public static void subFind(int first, int last) {
		check(first);
		check(last);
		if (Math.min(last - first - 1, (int) a[last-1] - (int) a[first]) >= 1
				&& ((int) a[first] < (last + 1) - 1 && (int) a[last] > (first + 1) + 1)) {
			int i = (first + last) / 2;
			if (first + 1 == i) {
				check(i);
			} else {
				subFind(first + 1, i);
			}
			if (i + 1 == last - 1) {
				check(i + 1);
			} else if (i + 1 < last - 1) {
				subFind(i + 1, last - 1);
			}
		}
	}

	public static void check(int index) {
		System.out.printf("##check %d ##\n", index+1);
		if (a[index] == index + 1) {
			System.out.printf("a%d\n", index+1);
		}
	}
}

-0.9, -0.6, 0, 0.2, 0.3, 6, 6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14
打印为
##check 1 ##
##check 14 ##
a14
##check 2 ##
##check 7 ##
##check 3 ##
##check 4 ##
##check 5 ##
##check 6 ##
a6
##check 8 ##
##check 13 ##
##check 9 ##
##check 10 ##
##check 11 ##
a11
##check 12 ##
很不巧，每个元素都检查了

-0.9, -0.6, 0, 0.2, 0.3, 6, 6.1, 6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 11, 11.1, 11.2, 14
打印为
##check 1 ##
##check 18 ##
##check 2 ##
##check 9 ##
##check 3 ##
##check 5 ##
##check 6 ##
a6
##check 8 ##
##check 10 ##
##check 17 ##
只检查了部分

2013年9月23日 20:05

GQM
96
0 0 7

• 6条评论

0 0

	// 6,11,14,19   注意:从14之后开始,"下标"是是小于"内容",但是最终在19相等了
	public static double[] ff = new double[] { -1, -0.9, -0.6, 0, 0.2, 0.3, 6,
			6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14, 16, 17, 17.1, 18.2, 19 };

这个问题,二分法貌似不太适用,
用二分法,无法是在 A[n]=m  ; n>m 或者 n<m之间找区间,

但是看上面的这个数组.上面的数组会在6,11,14,19的时候出现 n=m的情况

n<=14以前,都是n>=m;
但是到了   14<n<=19 这个区间,都是n<=m的.

所以区间法(二分法)不靠谱.

所以我觉得用hash比较靠谱

2013年9月23日 19:28

414149609
17
0 0 3

• 1条评论

0 0

我也来贴一段伪代码：
int index = 0;
while(index < nums.length) {
    double value = nums[index];
    int n = (int) value;
    if (n != value || index > n) {
        index ++;
        continue;
    }
    if (index == n) {
        System.out.println(index);//打印下标
        index ++;
        continue;
    }
    index = n;
}

2013年9月23日 17:28

zrz_1989
2
0 0 6

• 1条评论

0 0

楼上正解，二分法找出符合条件的数组下标区间，再在这个区间内匹配！

2013年9月23日 10:28

zhang4044
20
0 0 1

• 添加评论

0 0

我这里有个log(n)的算法：http://openmind.iteye.com/blog/1320859

2013年9月23日 10:09

OpenMind
704
0 1 13

• 3条评论

0 0

数组B[i]是数组A[i]的降序排列，
if(0==B[i]-A[i])
  那么必然A[i]=i

2013年9月23日 00:06

511039003
17
0 0 3

• 1条评论

0 0

我的想法是加强你题目的条件，假设你的数组是整形数组
然后做以下推理：
1）对任一元素A[i]，若i<A[i]，则对任意i'>i不存在A[i']=i'
2）对任一元素A[i]，若i>A[i]，则对任意i'<i不存在A[i']=i'
3）假设存在A[i]=i,A[j]=j，i<>j，不妨设i<j，则对任意i<=i'<=j，都满足A[i']=i'
4）假设存在A[i]=i,A[j]=j，i<>j，不妨设i<j，则不存在i',满足i<i'<j，A[i']<>i'
以上几点都容易证明，
1）指的是A[i]在i的右侧时，右侧不存在符合的值
2）指的是A[i]在i的左侧时，左侧不存在符合的值
3）和4）指的是如何存在，只可能是唯一的一段连续整型的下标符合条件的值
于是命题是找到最小的l符合A[l]=l和最大的r符合A[r]=r
为此可以先找到l至r段中任意一个元素m，然后分别找m两边的l和r
findm(a,b):找到元素m,用推断1和2及二分法找到第一个满足A[i]=i的值；即若二分点i=A[i]，则m=i，然后找l和r，返回；否则若i<A[i]，则b=i；若i>A[i]，则a=i，继续findm(a,b)；
findm(a,b):
  i=(a+b)/2;
  if i=A[i]: m=i; findLeft(a,m); findRight(m,b); return;
  if a+1>=b: return;
  if i<A[i]: findm(a,i);
  else: findm(i,b);

findleft(a,m):找到元素l，用推断3和4及二分法找A[i]=i，并不断修正，即若二分点i满足A[i]=i，则m=i，若不满足，则a=i；继续findLeft(a,m)，直到a=m为止，置l=m；
findLeft(a,m):
  if a=m: l=m; return;
  i=(a+m)/2;#下取整
  if i=A[i]:findLeft(a,i);
  else: findLeft(i,m);
 
findRight(m,b):找到元素r，用推断3和4及二分法找A[i]=i，并不断修正，即若二分点i满足A[i]=i，则m=i，若不满足，则b=i；继续findRight(m,b)，直到b=m为止，置r=m；
findRight(m,b):
  if b=m; r=m; return;
   i=(m+b)/2;#上取整
  if i=A[i]:findRight(i,b);
  else: findRight(m, i);

时间复杂度可参考二分法的

2013年9月23日 00:05

GQM
96
0 0 7

• 3条评论

0 0

差不多这个意思，没优化，只实现功能了，凑合看吧。。。
因两两不相等，且升序，那么 a【i】 == i 的，都是前面连续的。

public static final int[] a = new int[]
	{ 1, 2, 3, 7, 8, 9 };

	public static void main(String[] args)
	{
		int x = 1, y = a.length, j = 0;

		if (a[y - 1] == y)
		{
			// 全都是
			System.out.println(y);
		} else
		{
			while (x != y)
			{
				j = (y + x) / 2;
				if (a[j - 1] == j)
				{
					x = j;
					if (x + 1 == y)
					{
						x = y;
					}
				} else
				{
					y = j;
				}
			}
			System.out.println(j);
		}
	}

2013年9月22日 23:03

id.alex
10
0 1 10

• 4条评论

0 0

如果这是一个整形的数组，二分法应该很快很快

2013年9月22日 16:42

zhangzhenjj
55
0 0 5

• 2条评论

0 0

高效是指时间复杂度低吗，2分查找

2013年9月22日 16:30

wanghuanqiu
630
0 1 35

• 1条评论