Chris

在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。
直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，这需要两次遍历，然后再遍历一次原数组，将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

给出这个解答后，面试官有要求只能用一个辅助数组，且要求少用一次遍历。想了半天没想出来，后来在面试官的提示下得出解，今天实现了一下。

见代码：

#include <iostream>
 
using namespace std;
 
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
 
void findNum(int data[],int len)
{
	int* a = new int[len];
	int* b = new int[len];
	a[len-1] = data[len-1];
	for (int i = len-2;i > 0;i--)
	{
		a[i] = min(data[i],a[i+1]);
	}
 
	if (data[0] <= a[1])
	{
		cout<<"0:"<<data[0]<<endl;
	}
 
	a[0] = data[0];
	if (data[1] >= a[0] && data[1] <= a[2])
	{
		cout<<"1:"<<data[1]<<endl;
	}
 
	for (int i = 1;i < len-2;i++)
	{
		a[i] = max(data[i],a[i-1]);
		if (data[i+1] >= a[i] && data[i+1] <= a[i+2])
		{
			cout<<i+1<<":"<<data[i+1]<<endl;
		}
	}
	a[len-2] = max(data[len-2],a[len-3]);
	if (data[len-1] >= a[len-2])
	{
		cout<<len-1<<":"<<data[len-1]<<endl;
	}
}
 
int main()
{
	int data[10] = {1,3,2,4,6,7,5,9,11,10};
	findNum(data,10);
}

在CSDN算法版看到的题目，据说是MS的笔试题。

题目是这样的：

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

NASH说了个想法，很直观，用O(logN)找到原序列的起点，再用O(logN)找到要找的点（做一些下标控制）。应该可以，我没有实现，BAD说这叫化未知问题为已知问题，嗯，不错。

我自己写了另一个解法，单纯的二分查找，只不过判断该左转还是右转的时候需要谨慎一些，把所有情况都考虑到自然就没有问题了。

在此序列不断二分的过程中，由于原序列是一个递减序列经过旋转得到的，将它从任何位置分开，都会得到两个序列，其中一个是递减序列，另一个可以通过一个递减序列通过旋转得到。这样在不断地二分查找时，我们处理的序列子片段要么就是一个旋转后递减序列，要么就是一个纯递减序列，而无论是前者还是后者，在继续分成两个片段时，至少有一个纯递减序列（可能两个都是，如果之前的序列片段就是纯递减序列的话）。这样我们可以保证能找到一个片段是纯递减序列（if(data[i]>=data[j])），然后判断我们要找的数是否在这个片段中（这是很直观的，if(data[i]< =num&&num<=data[j])），如果在则继续在此片段中查找，否则说明在另一个序列中，则递归在其中查找。

代码如下：
Continue reading »