一道数组面试题-不能使用辅助空间找重复次数的数

浪子一号 发布于 2013/10/17 15:52
阅读 2K+
收藏 6

今天小弟去面试一个java后台职位。期间遇到了笔试题了。老实说,都很久没有做过笔试题了,之前找工作都是朋友推荐,过去聊聊技术的。今天遇到面试题,我就知道了会回答的不好的了。毕竟做面试题还是需要复习的。

废话少说上题:

有一个长度为50的数组,里面的数都是1-20.设计一个算法 将重复次数最多的那个数找出来,算法复杂度要求O(n).不能使用辅助空间。


其实我这里还是不太明白:不能使用辅助空间的意思 一个变量都不能使用么??? 这是这样 那么怎么循环遍历数组呢

ps:提示各位面试的时候一定要复习基础知识。不然若如果你在某个领域上做了好几年。肯定忘记了一些基础知识,但是面试的时候就有可能遇到。比如 java的锁。当年读大学的时候我还很深入的研究过操作系统的各种锁机制和java的锁机制。毕业几年了。写j2ee很少遇到自己写锁同步的事情。结果都荒废了。面试的时候问到了,都几乎搭不上话。丢脸

各位看官 接招吧

加载中
0
Anger_Coder
Anger_Coder
请教一个问题,就是数组中元素的顺序已经确定了吗?还是乱序的
0
Shazi199
Shazi199
import java.util.Random;

public class FindMax {
	int[] source = new int[50];

	public FindMax() {
		Random rand = new Random();
		for (int i = 0; i < 50; i++) {
			source[i] = rand.nextInt(20) + 1;
		}
	}

	public int getMaxTest() {
		int[] check = new int[20];
		for (int i = 0; i < 20; i++) {
			check[i] = 0;
		}
		int max = 0;
		for (int i = 0; i < 50; i++) {
			check[source[i] - 1] += 1;
			if (check[max] < check[source[i] - 1]) {
				max = source[i] - 1;
			}
		}
		return max + 1;
	}

	public int getMax() {
		for (; getExtra(21) < 50; setExtra(21, getExtra(21) + 1)) {
			setExtra(getBase(getExtra(21)), getExtra(getBase(getExtra(21))) + 1);
			if (getExtra(getExtra(0)) < getExtra(getBase(getExtra(21)))) {
				setExtra(0, getBase(getExtra(21)));
			}
		}
		return getExtra(0);
	}

	public int getBase(int i) {
		return source[i] % 100;
	}

	public int getExtra(int i) {
		return source[i] / 100;
	}

	public void setExtra(int i, int extra) {
		source[i] = extra * 100 + getBase(i);
	}

	public static void main(String[] args) {
		FindMax fm = new FindMax();
		System.out.println(fm.getMaxTest());
		System.out.println(fm.getMax());
	}
}

 

主要思想就是利用冗余空间。应该算是符合O(n)和不用辅助空间的要求吧。

为了代码更易阅读用了几个get和set方法代替了一些语句。

缺陷:若出现次数最多的数大于一个,只能返回最近更新计数器的那个。

悠悠然然
悠悠然然
回复 @Shazi199 : 呵呵,果然没有看仔细,不好意思
Shazi199
Shazi199
回复 @悠悠然然 : 你没仔细看么,这是单元测试用的
悠悠然然
悠悠然然
int[] check = new int[20]; 这里不满足条件 。
0
RegnoiX
RegnoiX

遍历数组在对应的index下加21,再遍历1到20项 除以21 

不知道对不对

0
修改登录密码
修改登录密码

有个比较笨的办法

先遍历整个数组,对每个元素(假定为x),找到对应的第x个素数prime(x)

把所有的prime(x)都乘起来得到一个大数y; 这是个o(n)的过程

然后再使用i从1到20遍历,用y除以每个prime(i) 可以计算出 这个y中包含多少个i

记录下最大的那个值就可以了



0
修改登录密码
修改登录密码

还有个比较投机的办法,用数组的0-19的每个元素的高4位存储对应的个数

for (i=0; i<50; i++)

{

    x=array[i];

    n=array[x]>>4;

    array[x] |= (n+1)<<4;

};

max=0;

for (i=0; i<20; i++)

  if (  (array[i]>>4  ) >( array[max]>>4)

         max=i;

printf( max);

修改登录密码
修改登录密码
辅助存储空间是说不需要开辟其他存储空间(像数组 链表 ) 局部变量一般不算存储空间。 如果你还不确定,你可以直接问考官是否局部变量是否可以使用。
浪子一号
浪子一号
我觉得答案的思路就是你这样。但是不用辅助空间的意思叫什么呢?? 你还是用了 i 的变量来做啊
0
卖切糕大叔
卖切糕大叔

我写的这个除了循环控制之外没有申请任何内存,复杂度是O(n)

public class sb {

	public static void findTheShit(int[] array) {
		for(int i = 0; i < array.length; i++)
			array[array[i] % 20 ==0 ? 20 : (array[i] % 20)] += 20;

		array[0] = 0;
		for(int i = 1; i <= 20; i++) {
			if(array[0] < (int)((array[i] - 1) / 20))
				array[0] = (int)((array[i] - 1) / 20);
		}
		
		System.out.println("---出现次数最多的数字(" + array[0]  + "次)---");
		for(int i = 1; i <= 20; i++) {
			if(array[0] * 20 < array[i])
				System.out.println(i);
		}
	}

	public static void main(String[] args) {
		int[] rand = new int[50];
		for(int i = 0; i < 50; i++) {
			rand[i] = (int)(Math.random() * 20) + 1;
			System.out.print(rand[i] + "\t");
		}
		System.out.println();
		findTheShit(rand);
	}
}

WeirdBIrd
WeirdBIrd
类名 。。v587
卖切糕大叔
卖切糕大叔
回复 @eel : 细细想来第一个循环可以省掉,我改进了一下,现在是完美O(n)
修改登录密码
修改登录密码
你这个复杂度肯定不是O(n) 有个两重for循环 复杂度应该是O(m*n) n,m分别是数的值域和数组的大小
悠悠然然
悠悠然然
回复 @你們為何那麼吊 : 强,这都被你发现了。
军区文工团
军区文工团
类名取的是高端大气上档次
0
算法与编程之美
算法与编程之美

引用来自“卖切糕大叔”的答案

我写的这个除了循环控制之外没有申请任何内存,复杂度是O(n)

public class sb {

	public static void findTheShit(int[] array) {
		for(int i = 0; i < array.length; i++)
			array[array[i] % 20 ==0 ? 20 : (array[i] % 20)] += 20;

		array[0] = 0;
		for(int i = 1; i <= 20; i++) {
			if(array[0] < (int)((array[i] - 1) / 20))
				array[0] = (int)((array[i] - 1) / 20);
		}
		
		System.out.println("---出现次数最多的数字(" + array[0]  + "次)---");
		for(int i = 1; i <= 20; i++) {
			if(array[0] * 20 < array[i])
				System.out.println(i);
		}
	}

	public static void main(String[] args) {
		int[] rand = new int[50];
		for(int i = 0; i < 50; i++) {
			rand[i] = (int)(Math.random() * 20) + 1;
			System.out.print(rand[i] + "\t");
		}
		System.out.println();
		findTheShit(rand);
	}
}

这个思路非常好,非常不错,谢谢楼上分享。

不过还是可以改进一下,直接用0-19来存放1-20数字,没有必要从1-20。

下面这个算法用a[n-1]存放出现次数最大值,a[n-2]存放出现次数最多的值。

void calc_max_num(int *a, int n){
	int i = 0;

	while(i < n){	
		a[a[i] % 20] += 20;
		++i;
	}

	a[n-1] = 0;//存放出现的次数最大值
	a[n-2] = 0;//存放出现次数最多的数值

	i = 0;
	while( i < 20){
		if(a[i]/20 > a[n-1]){
			a[n-2] = i;
			a[n-1] = a[i]/20;
			
		}
		++i;
	}
	printf("The num is: %d\n", a[n-2] == 0 ? 20 : a[n-2]);
	printf("The max occurrence is: %d\n", a[n-1]);

}

算法与编程之美
算法与编程之美
回复 @zhoulc : 是这样的,当时写的代码没有考虑到出现次数相同这种情况,谢谢你的提醒。
zhoulc
zhoulc
这个应该返回的是个数组吧,可能有某几个数,出现次数一样,并且都是出现最多的次数
算法与编程之美
算法与编程之美
回复 @卖切糕大叔 : 的确会出现这种情况,我没考虑到,谢谢。
卖切糕大叔
卖切糕大叔
我第三个循环的目的就是能找出最多次出现数字不唯一的情况;你也可以改进一下
算法与编程之美
算法与编程之美
回复 @flydom : thanks.
下一页
0
悠悠然然
悠悠然然
个人对这个面试出题比较BS,除了显摆一下技巧,基本没有什么实际意义。
0
仪山湖
仪山湖

有一个长度为50的数组,里面的数都是1-20.设计一个算法 将重复次数最多的那个数找出来,算法复杂度要求O(n).不能使用辅助空间。
说明最多有20个不同的数字,在长度为50的数组里,为20个不同的数字计数,看起来很简单,不过,这里没有说数组是有序还是无序的,在实现上还是一定难度的,一个大体的思路是:

扫描数组A,对于数组中的任意一元素 n = a[i], 0<n<=20, 把a[i]和a[n]互换,把a[n]处设置-1,如果a[n]处已经是-1,则a[n]--,以同样的方式计算a[i], 若有交换,记为a[n'],保留a[n]和a[n']之间绝对值大者所对应的数组索引到变量m中,如果没有交换发生,i++,重复上面的过程,只到数组扫描完成。

0
汤医森
汤医森

可以考虑利用位运算挖掘空间,虽然现实可行但是感觉有点走偏了。基本思路:将数组的0-19 的低6位作为map统计出现频率,为了避免冲突,对前20个数左移6位,由于2^6=64>50,因此这6位足够统计50个数字的频率,统计结束之后再利用数组20、21位置统计最大频度及最大频度的数字,时间复杂度仍为O(n)

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
    //Generate 50 numbers ranging from 1-20
    srand( clock() );

    int a[50];
    int counter[20] = {0};

    cout<<"Original array:"<<endl;
    for( int i=0;i<50;i++ ) {
        a[i] = rand()%20+1;
        cout<<a[i]<<" ";
        counter[a[i]-1]++;
    }
    cout<<"\n===== END ======"<<endl;

    // Dumb method to check real top number
    {
        int maxCounter = 0;
        int maxNumber = 0;
        for( int i=0;i<20; i++ )
        {
            if( counter[i]>maxCounter ) {
                maxCounter = counter[i];
                maxNumber = i+1;
            }
        }
        cout<<" Real max number:"<<maxNumber<<" appear="<<maxCounter<<endl;
    }

    // Raise previous 20 elements by 6 bit as counter, as 2^64>50
    for( int i=0;i<20;i++ ) a[i]<<=6;

    // Count previous 20 elements
    for( int i=0;i<20;i++ ) a[ ((a[i]>>6)-1) ]++;

    for( int i=20;i<50;i++ ) a[ a[i]-1 ] ++;

    // Take a[20] as max counter
    int &maxCnt = a[20];
    // Remember max in a[21]
    int &maxNumber = a[21];

    maxCnt = 0;
    maxNumber = 0;
    for( int i=0;i<20;i++ ) {
        if( (a[i]&0x3f) >maxCnt )
        {
            maxCnt = a[i]&0x3f;
            maxNumber = i+1;
        }
    }

    cout<<"The max number is: "<<maxNumber<<" appear="<<maxCnt<<endl;
    return 0;
}

汤医森
汤医森
前半部分使用最直接的思路找出最大频数,以用于验证结果的正确性,不要看错哟
返回顶部
顶部