一路程序题的反思——一些为了减少内存的开销

一道程序题的反思——一些为了减少内存的开销

已知含有N个元素的一个数组，数组中各元素的范围是1~N-1，找出重复的那个值。

（就是有N-1个数都填充到N个位置，这N-1个

数至少出现一次，就是说，肯定有哪个数出现了两次，把这个数找出来。

这道题，在去年冬天的澡堂里，同学和我讨论过，就是建一个一样大的数组，将原来的数组遍历一遍，相应的位置

置1，当再次置1时，返现已经是1时，这就是那个数。

但是我一般一定会用int a[N]。

看到某位大神用bit来标识是否已存在，顿时感觉差距好大。

以下是代码：

我稍微做了一些修改：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <windows.h>
#define tyust 0
int produce_value(int a[],int N);

int main()
{
	int a[50];

	int i,same_num,site,p_value;

	same_num=-1;
	site=-1;

	for (i=0;i<50;i++)
	{
		a[i]=i+1;
	}


	while(!((same_num>0)&&(site>-1)&&(same_num!=(site+1))))
	{
		srand((unsigned)time(NULL)); 

	    a[site=(rand()%50)]=(same_num=(rand()%50)+1);

	}



	for (i=0;i<50;i++)
	{
		printf("%d  ",a[i]);

		if (((i+1)%10)==0)
		{
			printf("\n");
		}
	}

	printf("same_num=%d,site=%d\n",same_num,site);

	p_value=produce_value(a,50);


	printf("the produce value is %d\n",p_value);
	


}

int produce_value(int a[],int N)
{
	int n=N;
	int *array=a;
	int value=0;
    int a_num;
	int * p;
	int i;

	assert((n>0)&&(array!=NULL));
	a_num=(n/32)+1;

	assert(a_num>0);

	p=(int*)malloc(sizeof(int)*a_num);
	address=p;

	for (i=0;i<a_num;i++)
	{
		p[i]=0;
	}


	for (i=0;i<n;i++)
	{
		
		if (((p[(a[i]/32)])&(1<<(32-(a[i]%32))))==0)
		{
			
			p[(a[i]/32)]|=(1<<(32-(a[i]%32)));
		}
		else
		{
			value=a[i];
			free(p);
			return value;
		}

	
	}

	return -1;

}

看结果

本题用到了。malloc就是动态开了一片堆。这次没有忘记使用free（）。

使用了，assert（）进行实参的合法性检验。

使用随机函数来产生位置和数字。