- 论坛徽章:
- 0
|
[这个贴子最后由samhoo在 2002/10/28 12:04pm 编辑]
问题：给定一个数组long L[1000],且已知X是其中的一个元素，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
有没有办法做到呢？
--------------------------修改--------------------------------------------------
题目：给定一个数组long L[n],且已知X是其中的一个元素(等于X的元素可能不止一个)，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
提示:
A）为了能使讨论能集中于算法本身，而不是无关主旨的细节，下面附上模板程序，只需实现Partition函数即可验证程序是否正确。
B）如果大家能遵守一定的“八股”，我们沟通的效率会高些。(事实上,没有多少人可以有耐心看别人的代码，能看看算法以及测试结果就不错了,下面的“八股”直面这一事实)
八股：
一）算法说明
二）编译运行平台，机器类型/主频
三）Partition函数代码
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
ii )n=10的随机数组
iii)n=10,000,000的随机数组
iv )n=50,000,000的随机数组(小心，别影响别人工作)
v ）其他自己认为具有“边界”特性的数组。
模板程序：
#include<string.h>;
#include<stdio.h>;
#include<stdlib.h>;
#include<time.h>;
#define DISPLAY \
{ \
int i; \
printf("L[]=" ; \
for (i = 0; i < num; i++){ \
if (i >; 20 ){ \
printf("...(too much number, ignore)"; \
break; \
} \
printf("%d ", L); \
} \
printf("\n"; \
}
int Partition(long *L, int n, long X); /* 实现这个函数 */
long *MakeRandomList(int *num);
long *CreateList(int n);
int Check(long *L, int num, int X, int position);
int SWAP(long *L, int a, int b);
int main()
{
long X;
long *L;
//long L[]={5,5,5,5,5,5,7,1,6,8};
int num = 10;
int pos = 0;
clock_t start_time, end_time;
double duration;
L=MakeRandomList(&num);
X = L[(num - 1) / 2];
printf("X=%ld\n", X);
DISPLAY
printf("-----------------------------------------------------------------\n";
start_time=clock();
pos = Partition(L, num, X);
end_time=clock();
printf("Check :";
if (Check(L, num, X, pos))
printf("incorrect.\n";
else
printf("correct.\n";
duration = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time : %.3f seconds.\n", duration);
printf("-----------------------------------------------------------------\n";
printf("position=%ld\n", pos);
DISPLAY
free(L);
return 0;
}
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
//在这里插入你的代码
}
long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
long *L;
L = (long *) malloc( n * sizeof(long) );
if( L == NULL) { /* Exit program if memory cannot be allocated */
printf("\nCannot allocate enough memory for list.\n";
exit(0);
}
return (L);
}
long *MakeRandomList(int *num)
{
long *L; /* pointer to List */
unsigned int seed; /* seed for random number generator */
int i; /* index of for loop */
printf("\nNumber of elements to sort=>;";
scanf("%d",num);
printf("Seed for random number generator (integer)=>;");
scanf("%d",&seed);
srand(seed);
/* Allocate memory for # of elements. If memory cannot be allocated,
display message and terminate program. Read in the elements. */
L = CreateList(*num);
if (L == NULL) {
printf("\nCannot allocate enough memory for number list.\n");
exit(0);
}
for (i = 0; i < *num; ++i)
L = rand();
return(L); /* Return the List */
}
int Check(long *L, int num, int X, int position)
{
int i, lpos = -1, rpos = -1;
for (i = 0; i < num; i++)
if (L == X){
lpos = i;
break;
}
else if (L >; X)
return -1;
for (i = num - 1; i >;= 0; i--)
if (L == X){
rpos = i;
break;
}
else if (L < X)
return -1;
if ((lpos == -1) || (rpos == -1) || (position < lpos) || (position >;rpos))
return -1;
for (i = lpos; i <=rpos; i++)
if (L != X)
return -1;
return 0;
}
int SWAP(long *L, int a, int b)
{
long temp;
temp = L[a];
L[a] = L;
L = temp;
return 0;
}
|
|
免费注册
发表于 2002-10-22 20:23
