mergedistinct.cpp

利用归并排序检查输入的数值是否有相同值,方法是在归并排序的过程中边排边判断

#include <iostream>
using namespace std;

int MAX_REC_NUM=9999;

bool merge(int nums[], int low, int m, int high){
	int A[10];
	int i=low;
	int j=m+1;
	int k=1;
	while(i<=m&&j<=high){
		if(nums[i]==nums[j]){
			return false;
			}
		else if(nums[i]>nums[j])
				A[k++]=nums[j++];
			else
				A[k++]=nums[i++];
	}
	while(i<=m)
		A[k++]=nums[i++];
	while(j<=high)
		A[k++]=nums[j++];
	for(k=1,i=low;i<=high;k++,i++)
		nums[i]=A[k];
	return true;
}


bool merge_distinct(int nums[],int n){
	int len=1;
	int i;
	while(len<n){
		for(i=1;i+2*len-1<=n;i=i+2*len)
			if(merge(nums,i,i+len-1,i+2*len-1)==false){
				return false;
			}
		if(i+len-1<n)
			if(merge(nums,i,i+len-1,n)==false){
				return false;
			}
		len*=2;
	}
	return true;
}


int main(){
	int a[100];	
	a[1]=-1;
	int i=1;

	do{
	cin>>a[i];
	}
	while(a[i++]!=-1);
	bool distinct;
	if(i>=4){
		distinct=merge_distinct(a,i-2);
		if(distinct)
			cout<<"the numbers are distinct"<<endl;
		else
			cout<<"the numbers aren't distinct"<<endl;
	}
	return 0;
}