北林OJ——260二维数组中元素的查重

#include<iostream>
#include <iomanip>

using namespace std;
#define OK 1
#define ERROR 0
#define MaxSize 100
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//typedef double ElemType;
typedef  int Status;
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//假设是大堆
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 +1;//左孩子下标

	while (parent<n)
	{
		//找到左右孩子中较大的
		if ((child + 1 < n) && a[child + 1] > a[child])//注意：是否有右孩子
			child++;
		//假设是大堆
		if (child<n&&a[parent] < a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void HeapSort(HPDataType* arr, int n)
{
	//2.1在原有数组的基础上构建堆
	//如果要排成升序，需要构建大堆，将堆顶元素与最后一个元素交换，向下调整
	//再将堆顶元素与倒数第二个元素交换，向下调整
	//时间复杂度度：N*logN,空间复杂度：O（1）
	
	//第二种
	////向上调整建堆——数组第一个元素默认是堆
	//for (int i = 1; i < n;i++)
	//{
	//	AdjustUp(arr, i);
	//}
	//向下调整建堆
	//找到倒数第一个非叶子节点的下标
	int parent = (n - 1 - 1) / 2;
	for (int i = parent; i >= 0; i--)
	{
		AdjustDown(arr, n, i);//定义中的n是元素的个数，用于计算下标
	}
	//堆顶元素与最后一个元素交换，向下调整
	int end = n - 1;
	while (end > 0)
	{
		//交换
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}

}
//判断排序好的数组相邻元素是否相等,如果有相等的，返回1
int IsEqual(HPDataType* arr,int n)
{
	int flag = 0;
	for (int i = 0; i < n; i++)
	{
		if (i + 1 < n && arr[i] == arr[i + 1])//存在下标为i的元素
		{
			flag = 1;
			break;
		}
	}
	return flag;
}
//设二维数组a[1..m, 1..n] 含有m*n 个整数。写一个算法判断a中所有元素是否互不相同。
void test260()
{
	int m, n,flag=0;
	do
	{
		cin >> m;
		cin >> n;
		if (n == 0 && m == 0)
			break;
		HPDataType* arr = new int[m * n];
		/*int* p = new int [10];*/
		for (int i = 0; i < n * m; i++)
		{
			cin >> arr[i];
		}

		//int size = sizeof(arr) / sizeof(HPDataType);
		// //sizeof(arr)计算的是指针所占字节，为4或8
		int size = m * n;
		HeapSort(arr, size);
		flag=IsEqual(arr, size);
		if (1 == flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	} while (1);

}

int main()
{
	test260();
	//test1();

	return 0;
}