主题：第42次编程比赛第二题
argentmoon [专家分：13260] 发布于 2006-09-22 12:48:00
[center]数字最少交换次数[/center]
第二题还是求最少次数，但问题描述却不一样了。
请问一个无序的数列按从小到大的序排好最少需要交换多少次数字才可以达到目的？
函数接口：
int Least(int a[], int n);
//a数组里面存有n个数，从a[0] ～ a[n – 1]，无序。
//函数返回最少交换次数
注：数据中不存在相同的数字，但数字有可能是负数。
注二：[color=FF0000]最少交换次数[/color]肯定存在，不因排序算法不同改变。
n<=10,000,000,内存限制100M.
示例
int a[] = {14, 7, 2, 0}
交换14和0, 交换7和2，数组就排好了序，所以最少交换次数是2.
回复列表 （共14个回复）
沙发
argentmoon [专家分：13260] 发布于 2006-09-22 12:09:00
test
板凳
tenm [专家分：330] 发布于 2006-09-22 14:42:00
#include <stdlib.h>
#include <stdio.h>
int Least(int a[], int n)
{
int i,j,k,iright=0,ileft=0;
for(i=0;i<n;i++){
for(j=0,k=0;j<n;j++){
if(a[i]>a[j]) k++;
}
if(k>i) iright++;
if(k<i) ileft++;
}
return iright>=ileft?iright:ileft;
}
int main(int argc, char* argv[])
{
int i=0,a[8]={6,4,3,5,7,8,1};
i=Least(a,7);
printf("%d.\n",i);
system("PAUSE");
return 0;
}
3 楼
xieyong456 [专家分：2620] 发布于 2006-09-22 17:43:00
#include <stdio.h>
int Least(int a[], int n);
int Min(int a[], int j, int n);
void swap(int v[], int i, int j);
int main(void)
{
int a[8] = {7, 6, 8, 9, 3, 16, 18, 1};
printf("%d", Least(a, 8));
return 0;
}
int Least(int a[], int n)
{
int i, j;
int len;
int count = 0;
for(i = 0; i < n; i++)
{
j=i;
len = Min(a, j, n);
if(len == j)
{
;
}
else
{
swap(a, j, len);
count++;
}
}
return count;
}
int Min(int a[], int j, int n)
{
int min, i;
int k = 0;
min = a[j];
for(i = j; i < n; i++)
if(a[i] <= min)
{
min = a[i];
k = i;
}
return k;
}
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
4 楼
joekings [专家分：550] 发布于 2006-09-22 18:11:00
struct iplace
{
int value;
int place;
int pass;
};
int Least(int a[], int n)
{
int min,max,tmp=0;
int i=0,j=0;
max=a[0];
for(;i<n;i++)
{
if(a[i]>max)
{
max=a[i];
tmp=i;
}
}
iplace * b = new iplace[n];
b[n-1].value = max;
b[n-1].place = tmp;
if(tmp==n-1)
b[n-1].pass = 0;
else
b[n-1].pass = 1;
for(i=0;i<n-1;i++)
{
min=a[i];
tmp=i;
for(j=0;j<n;j++)
{
if(min>a[j])
{
min=a[j];
tmp=j;
}
}
b[i].value = min;
b[i].place = tmp;
if(tmp==i)
b[i].pass = 0;
a[i]=max;
}
tmp=0;
for(i=0;i<n;i++)
{
j=b[i].pass;
if(j==0) continue;
do
{
tmp++;
b[i].pass = 0;
i=b[i].place;
j=b[i].pass;
}while(j!=0);
}
delete [] b;
return tmp;
}
5 楼
hmq [专家分：70] 发布于 2006-09-22 22:35:00
int sort(int a[],int first)
{
if(first==last)
return 0;
if(a[first]==first)
return sort(a,first+1);
else
return 1+sort(a,first+1);
}
int least(int a[],int n)
{
int b[n],i,j,k,s,t;
for(i=0;i<n;i++)
b[i]=i;
for(i=0;i<n;i++)
{
k=b[i];
for(j=i;j<n;j++)
{
s=b[j];
if(a[k]>a[s])
{
t=k;
k=b[j];
b[j]=t;
}
}
b[i]=k;
}
return sort(b,0);
}由于没有装编译器，所以没有去调试，不知道有没有错误，不笑哦。
6 楼
bloodybg [专家分：1510] 发布于 2006-09-23 10:43:00
int Least(int a[], int n)
{
int i, j, count = 0;
int temp, min, min_sub;
for (j = 0; j < n; j ++)
{
min_sub = j;
min = 0;
for (i = j + 1; i < n; i ++)
{
temp = a[i] - a[j];
if (temp < min)
{
min = temp;
min_sub = i;
}
}
if (min_sub != j)
{
temp = a[j];
a[j] = a[min_sub];
a[min_sub] = temp;
count ++;
}
}
return count;
}
7 楼
wlsss [专家分：150] 发布于 2006-09-23 13:17:00
//当个数大于 5.9E6 的时候，就需要内存100M了
//当个数为 1E7 的时候，需要内存168M.
#include <stdlib.h>
#include <memory.h>
#include <iostream.h>
int hashSize;
struct SWAP
{
int num;
SWAP *next;
}*hashTable;
SWAP* GetHashRecord(int num)
{
int key=0;
if(num==0)
return &hashTable[0];
else
{
key=num%hashSize;
while(!(hashTable[key].num==0 && key!=0 || hashTable[key].num==num))
{
key++;
if(key==hashSize)
key=1;
}
hashTable[key].num=num;
return &hashTable[key];
}
}
int intcmp(const void* p1,const void * p2)
{
int *n1=(int*)p1;
int *n2=(int*)p2;
if(*n1<*n2)
return -1;
if(*n1>*n2)
return 1;
return 0;
}
int Least(int a[], int n)
{
int *b=new int[n];
memcpy(b,a,n*sizeof(int));
qsort(b,n,sizeof(int),intcmp);
hashSize=(int)(n*1.2);
hashTable=new SWAP[hashSize];
memset(hashTable,0,hashSize*sizeof(SWAP));
int changetime=n;
for(int i=0;i<n;i++)
{
SWAP *pa=GetHashRecord(a[i]);
GetHashRecord(b[i])->next=pa;
int num=pa->num;
SWAP *p=pa->next;
while(p!=NULL)
{
if(num==p->num)
{
changetime--;
break;
}
p=p->next;
}
}
return changetime;
}
void main()
{
int a[] = {14,7,2,0};
int b = Least(a,4);
cout<<b<<endl;
}
8 楼
iAkiak [专家分：8460] 发布于 2006-09-23 20:39:00
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{
int value;
int index;
int flag;
bool operator < (const Node &o) const
{
return value < o.value;
}
};
int Least(int a[], int n)
{
int i;
int count = 0;
vector<Node> map(n);
for (i = 0; i < n; i++)
{
map[i].value = a[i];
map[i].index = i;
map[i].flag = 0;
}
sort(map.begin(), map.end());
for (i = 0; i < n; i++)
{
if (!map[i].flag)
{
int id = map[i].index;
while(id != i)
{
map[id].flag = 1;
id = map[id].index;
count++;
}
}
}
return count;
}
9 楼
廖增祥 [专家分：3930] 发布于 2006-09-24 17:35:00
int Least(int a[], int n)
{
int num = 0; /*交换次数*/
int i, j;
int temp;
for(i = 0; i <= n - 2; i ++)
{
for(j = i + 1; j <= n - 1; j ++)
if(a[j] < a[i];
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
num ++;
}
}
return num; /*返回总的交换次数*/
}
10 楼
廖增祥 [专家分：3930] 发布于 2006-09-24 17:41:00
int Least(int a[], int n)
{
int num = 0; /*交换次数*/
int i, j;
for(i = 0; i <= n - 2; i ++)
{
for(j = i + 1; j <= n - 1; j ++)
if(a[j] < a[i];
{
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];
num ++;
}
}
return num; /*返回总的交换次数*/
}
我来回复
您所在位置：