昨晚的笔试题：
大概是这个意思：一个数组X[1,2,....NUM]里面存放NUM个随机数，现在要找出数组里面的最大数和最小数，有min和max两个变量保存结果
一个种思路：遍历数组，把每个元素和关键字比较，每次都要把元素和min和max比较
第二种思路：如果一个数比min小就不可能比max大，不用再和max比较，如果比max大则不会比min小，不再和min比较
题目是给代码的，大概意思就这样，问的是第二种代码比第一种代码平均减少了多少次比较，写出推导过程晚上要去面试，估计会问这道题目(我没做！)，求答案和推导过程（我觉得能平均减少NUM/2次数）
大概是这个意思：一个数组X[1,2,....NUM]里面存放NUM个随机数，现在要找出数组里面的最大数和最小数，有min和max两个变量保存结果
一个种思路：遍历数组，把每个元素和关键字比较，每次都要把元素和min和max比较
第二种思路：如果一个数比min小就不可能比max大，不用再和max比较，如果比max大则不会比min小，不再和min比较
题目是给代码的，大概意思就这样，问的是第二种代码比第一种代码平均减少了多少次比较，写出推导过程晚上要去面试，估计会问这道题目(我没做！)，求答案和推导过程（我觉得能平均减少NUM/2次数）
#include<stdlib.h>void main()
{
int num[20];//用来存放随机产生的20个数
int i,j,sum,max,min,average;//sum,max,min,average分别用来存放总和，最大，最小及平均值
srand(100);
for(i=0;i<20;i++)
num[i]=rand()%100+1;
max=num[0];
min=num[0];
sum=0;
for(i=0;i<20;i++)
{ if(max<mun[i]) max=num[i];
if(min>num[i]) min=num[i]；
sum=sum+num[i];
}
average=sum/20.0;
j=1;
for(i=0;i<20;i++)//输出20个数，5个一行
{ printf("%d ",num[i]);
j++;
if(j==5) printf("/n");
}
printf("最大值为：%d,最小值为：%d,平均值为：%f",max,min,average);
pringf("/n");
}
第二种思路，我对题意并不是很了解，要么先比较min要么先比较max，你的意思是先随机比较哪个么？
max=X.Max();
若原先需要比较2 * NUM次
那么最少只用比NUM次,最多还是2 * NUM
则答案是NUM/2
最少a次，最多b次，平均就一定是(a+b)/2次么...
又不是线性分布的
第二种就是第一种的优化
最少比较Num次，最多比较2*Num次
平均不知道怎么算啊
难道是(Num + 2*Num )/2??
第二种：(num-1)*1用编程方式来表示就是：
min=max=array[0];
for(int i=1;i<array.Length;i++)
第一种：if(array[i]<min) min=array[i];if(array[i]>max)max=array[i];
第二种：if(array[i]<min) min=array[i];else if(array[i]>max)max=array[i];
第二种每个最少比较一次，最多两次 即Num~2*Num
结果
比如楼上的解答，为什么else if 是50%执行的？这就很难解释清楚。
楼主面试的话可以提出另外一种算法，因为这种方法是不稳定地减少NUM/2的比较次数。
有一种算法是稳定地减少NUM/2的比较次数：
每次取2个数，比如A和B，比较A和B，拿小的和min比较，拿大的和max比较。
这样NUM个数分成NUM/2个组，每个组比较3次，这样也能减少NUM/2的比较次数
1、数字array[i]要么执行if要么执行else if，各占50%的概率
2、减少次数是不稳定，所以求的是一个概率
3、每次取2个数，多了2个比较：a)判断是否还存在2个数；b)比较A和B
第二种方法：先区前2个数做下比大小，1次，后面最理想的次数是(num-2），最不理想的次数是(num-2)*2比较次数num-1～2*num-3
结果是0～num-2次
要么执行if 要么执行else if 各占50的概率...
if( rand % 10 < 1) {...}
else {...}
我是不是可以说要么执行if 要么执行else，各占50%的概率？
2.我没说这个不好
3.你就不能从第一第二个开始比较么，何须知道剩下的有多少个数
比较A和B根本不会浪费比较次数。
LZ所述这样优化其实可能只是加了一个continue;
确实有更好的优化方式比如15L
static void Main(string[] args)
{
int[] array = new int[10];
Random r = new Random();
for (int i = 0; i < array.Length; i++)
{
array[i] = r.Next(100);
Console.Write(array[i] + " ");
}
int max = array[0];
int min = array[0];
int count = 0; Console.WriteLine();
for (int i = 1; i < array.Length; i++)
{
count++;
if (array[i] < min)
{
min = array[i];
continue;//其实就是这样优化了一个continue
}
count++;
if (array[i] > max)
{
max = array[i];
}
}
Console.WriteLine("Max={0} Min={1} count={2}", max, min, count);
Console.ReadKey();
}
我自己测试时候的代码既然题目给出了代码 那么代码1的执行次数
是 Num*2 还是 （Num-1）*2 还是17楼所述 1+(num-2)*2 LZ一看便知
那么其实这个题就是要算概率问题
这非常赞同16楼的第二条观点
不过肯定不是简单的50% 数学不行 继续关注此帖
对于找最大值，最多替换 Max 值 Num 次，最少替换 1 次。平均 (Num + 1)/2替换最小值后，就不再去和最大值比较。
替换最大值后，就不再去和最小值比较。
但是这两个条件有先后，只能选择其中一种作为算法。无论选择哪种，都能比原来省下 (Num + 1)/2 次比较。
if(array[i]<min){}else if(array[i]>max){}啥都不说了。
比如你110跨栏的时间 或者我110跨栏的时间
min是一个 特定的数 他比较了i-1个数 才成就了这个min
比如刘翔110跨栏的时间你说array[i]有50%的可能性比min小？
题目里面的if (next<min)
{
noNeedCompareMin();
}
if (next>max)
{
noNeedCompareMax();
}
以先比较最小的为例，如果这个数比当前最小的还要小，自然它会是当前最小的，所以没必要比较最大值了，，
但是如果是比当前最小的要大，那么至于它是不是比最大值要大，第二个判断都是要做的，（next>max）..
对于先比较max也是同理。。所以减少的次数就只需要考虑一种情况，是这样。 比如 我们取第一个数当做最小数，那么只有后面的数比前面的最小数还要小的时候那就会有一次比较被节省下。
所以我们认为随即数任何两两大小都是50%的机会
那么 第二个数比第一个数小的概率就是1/2,
第三格数比前面2个最小数还要小的概率就是1/3,
同理对于M个随机数那么节省的次数就是
1/2+1/3+1/4+...+1/M
这题从结果来说的确是NUM/2没错，但你想当然的论证显然不能在面试中获得好的评分
array[i] 是个随机数，它只有2种可能：a)小于min，b)大于等于min这我笑了 如果MIN 是3， max 7 那么请问 如果现在array[i] =4 ， 天神下降了竟然会出现4这个第三种情况
第二种执行 if...else if... 的概率 100%+50% 解析过程如下：if (array[i]<min){//100%执行这个比较}else{//50%的情况执行else，因为是随机数，要么比min小，要么比min大（包括等于）
if(array[i]>max){ }//100%执行这个比较（别忘了这个100%包含在50%的可能里）
}
//执行比较语句的次数：100%+50%*100%
兄弟、你上面的写法是，
if(array[i]<min){}else if(array[i]>max){}
你现在改口说这个a)小于min，b)大于等于min
我读不懂你的意思了
我承认我不止一次的读错你的意思了。。
不过你要认为第i次数字 比前面最小的数值的大小概率如果是50%的话，那我真是汗了。
请你也看下24楼的我补充说24我的意思，再第二个if前面加一个else忘记写了如果第一个题目是2M的比较的话，
那么第二个题目是1/2+1/3+1/4+...+1/M
num/2吧，但我也不会写推导过程。
1 2*n
2 应该算是是二分法查找，两次 2*log2(n)节约的时间就是 2*n - 2*log2(n)数据结构的书上应该有算时间复杂度的，记不清了
这个题目也就变成了另外一个题目。一串随机数，在第i数是前面数字的最小数的概率是多少的问题了。 我认为随机数之间22平等，所以是1/i
所以就得出会节省的判断次数是
1/2+1/3+...1/M
当n很大时，括号里的部分就成了0.57721566490153286060651209叫做欧拉常数很多人都说优化了（n-1）/2之类的
你们太大看这个优化的效果了这题确实可以写出优化（n-1）/2的代码但是题目给出的那种优化方案优化不了那么多
(1/2+1/3+1/4+1/5+1/6+...1/n)/n
(1/2+1/3+1/4+1/5+1/6+...1/n)=0.57721566490153286060651209+ ln-1哎呀数学还给老师了 其实不完全理解
var min = 0;
var vcount = 0;
var flag = false;
var count = array.Length;
for (var i = 0; i < count / 2; i++)
{
vcount += 1;
if (!flag)
{
max = array[i] > array[count - i - 1] ? array[i] : array[count - i - 1];
min = array[i] < array[count - i - 1] ? array[i] : array[count - i - 1];
flag = true;
vcount += 2; }
else
{
vcount += 1;
if (array[i] > array[count - i - 1])
{
max = array[i] > max ? array[i] : max;
min = array[count - i - 1] < min ? array[count - i - 1] : min;
vcount += 2;
}
else
{
max = array[count - i - 1] > max ? array[count - i - 1] : max;
min = array[i] < min ? array[i] : min;
vcount += 2;
}
}
}
vcount += 1;
if (count % 2 != 0)
{
vcount += 2;
max = array[count / 2] > max ? array[count / 2] : max;
min = array[count / 2] < min ? array[count / 2] : min;
}
Console.WriteLine(string.Format("max:{0} min:{1} vcount:{2}", max.ToString(), min.ToString(),vcount.ToString()));
第二种方法，如果以
min = X[i];
max = X[i];
for(i =1;...)
{
if（X[i]<min）
{
min = X[i];
}
else if(X[i]>max)
{
max= X[i];
}
}这种形式比较。
得看数组里面最小值的位置，如果最小值在第一个，if语句每次都不true，都要对else if比较，总次数也是
2*（NUM-1），这是最差的情况；
如果数组是以降序排列，if语句每次都是true，那么只要进行（NUM-1）次比较，少了（NUM-1）；
再看，如果最小的值出现在中间第n个数处，那么从中间以后的数都要比较2次，后的比较次数为2*（NUM-n），但此时第n个前面的比较次数在（n-2）与2*(n-2)之间，与前面几个数中的最小值的分布有关。
由此看出，应该不是 NUM/2。
应该用数学归纳法来计算！
先吃饭去了
13L认为if(min<array[i]){}会被执行的概率是50%啊，第i个数只是要跟得到的min比较。这里只会有2种可能性，一种是比他大，一种是比他小。所以是50%啊。
楼上的是说第i个数为这第i个数中的最小值的概率是1/i。所以当他是最小值时，min过来的时候才不会去去执行else if这段代码。所以概率是1/i.
头晕，感觉是13L说得也是有点道理的。
else if，但是这个并不是说第n个前面的数都不执行else if，这得看第1到第n个数中，局部最小值的位置。
假如第1到第n个数是升序排列，那每次都会执行else if。
max = X[i];
for(i =1;...)
{
if（X[i]<min）
{
min = X[i];
}
else if(X[i]>max)
{
max= X[i];
}
}
以这种方式为方便起见，min是一个很大的数，max为一很小的数
num个数中，最小值的分布概率在各位置都是1/num
最小数在的位置 少的次数
1 f(1)=1
2 f(2) = 1 + 1
3 f(3) = 1/2概率为f(2) + 1/2概率为f(1) + 1
.
.
.
n f(n) = (f(n-1) + f(n-2)+....+f(1))/(n-1) +1
.
.
.
num f(num) = (f(num-1)+f(fun-2)+...+f(1))/(num-1)+1
每个都是1/num概率
求和得到平均少的次数
sum = (f(1)+f(2)+f(3)+...+f(num))/num
//max = 0;
for(i =1;...)
{
if（X[i]<min）
{
min = X[i];
}
else if(X[i]>max)
{
max= X[i];
}
}
以这种方式为方便起见，min是一个很大的数，max为一很小的数
num个数中，最小值的分布概率在各位置都是1/num
最小数在的位置 少的次数
1 f(1)=1
2 f(2) = 1 + 1
3 f(3) = 1/2概率为f(2) + 1/2概率为f(1) + 1
.
.
.
n f(n) = (f(n-1) + f(n-2)+....+f(1))/(n-1) +1
.
.
.
num f(num) = (f(num-1)+f(fun-2)+...+f(1))/(num-1)+1
每个都是1/num概率
求和得到平均少的次数
sum = (f(1)+f(2)+f(3)+...+f(num))/num
如果min = 5；
然后来判断 if（ x< 5） 基本不能true，也就是说要再执行else if，else if执行的概率当然不是50%另外，我这种说法只是反驳了你
但是数组是一开始就分布好的，并不是随机得到一个再比较一个的。
你这种思维方式是的不到答案的
也就是举例3个数字1,2,3
那么这三个数字排列组合后是3!=6种
1,2,3 ---这种情况，第一个数字就是最小数了后面没有比它小的 就没有节省的次数。以下同理
1,3,2 --- 节省数 0
2,1,3 ---1
2,3,1 ---1
3,2,1 ---2
3,1,2 ---16种情况总共可以节省5次那么请问是不是平均节省了5/6次呢。 不知道楼上的直接算是咋算出来的
你的min 一开始就是第一个数，而我的方法min一开始是一个很大的数，所以
1,2,3 ---这种情况，按照我的方法也是减少一次。
我一开始没看你在24楼的回答，所以没能完全理解你的算法。你这个答案是对的，只不过我们的比较方法不同。我刚刚按照我算的方法，如果min 一开始等于第一个数，得到的答案是与你一样的。
我的思路是先得到一个序列，然后假设最小值在每个位置的概率都是1/n，然后用数学归纳法算出来的。
更改下我的算法，如果min = 第一个数
最小数在的位置 减少的次数
1 f(1)=0
2 f(2) = 0 + 1
3 f(3) = 1/2概率为f(2) + 1/2概率为f(1) + 1
.
.
.
n f(n) = (f(n-1) + f(n-2)+....+f(1))/(n-1) +1
.
.
.
num f(num) = (f(num-1)+f(fun-2)+...+f(1))/(num-1)+1
每个都是1/num概率
求和得到平均少的次数
sum = (f(1)+f(2)+f(3)+...+f(num))/num
第一次，每一个数在进行比较前有3中情况：比MAX大，比MIN小，中间值。
现在解释先与MAX比较，在于MIN比较
if（num>max）
一次比较 //随机数，3分一得概率
if(num<max)
二次比较因此，n/3+2*n/3 = n减少了一半的比较时间
当数组中的元素为从小到大或从大到小排列时，会出问题。
举个例子：若数组x[NUM]里数据为{5,4,3,2,1}，设初始条件为min=10，max=0。
则按楼主的第二个思路运算下来，得到的结果为min=1，max=1。是不是算法上本身就存在问题呢？
如果值介于max和min还是要2个都比较的
过2天去图书馆借来看看！
明天终面啊，祝自己好运！
而最好情况是按从大到小顺序排序，这样除了第一次需要比较2次外，后面都是一次比较1次，这样就是num+1次。
这样2比1的最小和最大差距就是 2num - 2num = 0 和 2num-(num+1) = num - 1.
平均就是 (0 + 1 + 2 + ... + (num - 1)) / num
解就是(Num-1)/2
甚至这不是线性的。所以问平均减少多少次，无法回答。给他解析就行。
第二种：由于第一种方法每次都要与MAX与MIN比较，而第二种方法只要与其中一个比较就不需要与另一个比较了，所以每次比较就少了一次，N次下去就少N个比较，所以第二种方法的比较次数是N次。
终上所述，第二种方法比较第一种方法少2*N-N 次
第二种思路是N+（N+1）/2;
首先必须比较一次，假设先比较最小值，次数为N，第二次是否比较在于用多少次找到真正的最小值，根据每一次去数的概率都是1/N，求期望次数，可得：（1+2++N）*(1/N)=（N+1）/2,就是说平均（N+1）/2次比较才能找到最小值，这时不用和最大值比较;
不知道这种思路对不对，我数学也没学好。
第2种方法首先不管和min还是max比较，假定这里和min比较，进行n次，然后有1/2的概率要和max比较，所以是n+n/2 = 1.5n我认为是0.5n次
"java"
public class Test4 {
private static Random ran;
private int[] source;
private int min = 0;
private int max = 0;
private int compareCount = 0;
static{
ran = new Random();
}
public static void main(String...args){
Test4 t = new Test4();
t.init();
// t.printRan();
t.findMinMax(0);//2000
t.print();
t.findMinMax(1);//199X
t.print();
}
private void printRan() {
for(int i : source){
System.out.println(i);
}
}
private void init(){
//here I give 1000 numbers to test
source = new int[1000];
for(int i=0;i<source.length;i++){
source[i] = this.geneInt();
}
}
private int geneInt(){
return ran.nextInt();
}
private void print(){
System.out.println("Min:"+this.min);
System.out.println("Max:"+this.max);
System.out.println("compareCount："+this.compareCount);
}
private int getBig(int a,int b){
this.compareCount++;
return a>b?a:b;
}
private int getSmall(int a, int b){
this.compareCount++;
return a<b ?a:b;
}
/**
* @param mode 0 means if a is large than max, no need to compare with min, so vice versa
*/
private void findMinMax(int mode){
this.min = source[0];
this.max = source[0];
this.compareCount = 0;
if(mode==0){
for(int a: source){
this.max = this.getBig(a, this.max);
this.min = this.getSmall(a, this.min);
}
}
if(mode==1){
for(int a: source){
if(this.max<this.getBig(a, this.max)){
this.max = a;
}else if(this.min>this.getSmall(a, this.min)){
this.min = a;
}
}
}
}
}
我知道哪里错了，
假定先和max比较，则max越来越大，那么越往后面比较，则数比max大的概率要小于比max小的概率，并不是1/2的概率。至于怎么算，目前还不知道