左边的数都小于等 于它,右边的数都大于等于它

文章目录

1. 1. 题目
2. 2. 解析
3. 3. 代码
4. 4. 参考

题目

一个 int 数组,里面数据无任何限制,要求求出所有这样的数 a[i],其左边的数都小于等 于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现

解析

想其他的都是泪（递归、分治）
最妙的方法就是将原数组排序得到b，如果b[i]=a[i]，则a[i]就是满足该条件的数
这样正好满足只使用了一个额外数组^_^
最终的复杂度为O(nlogn)

代码

/** * 左边的数都小于等 于它,右边的数都大于等于它 * 将原数组排序b 如果a[i]=b[i] 则该i对应的值满足条件 * @param a */
 * 左边的数都小于等 于它,右边的数都大于等于它
 * 将原数组排序b 如果a[i]=b[i] 则该i对应的值满足条件
 * @param a
 */
public static void leftLtRightGt(int[] a){

	int[] b=a.clone();
	Arrays.sort(b);//O(nlogn)
	
	for(int i=0;i<a.length;i++)
	{
		if(a[i]==b[i])//只要相等 就表示满足条件
			System.out.println(i+":"+a[i]);
	}
}

参考

July 微软面试题 第81题

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权