找出重复的整数

谁借莪１个温暖的怀抱￠ 2022-05-19 11:40 195阅读 0赞

**在一个给定的数型组中，找出重复的整数:**

比如int array\[5\] = \{1,1,3,3,4,5,6\}重复的整数是1 ，3。

我的想法，先对数组进行排序，使数组处于有序状态，这样一来就容易判断重复的数字。我的判断方法是：用两个指针分别指向两个数字，比如用current指针指向第一个数字1next指针指向第二个数字1，如果current指向的数字等于next指向的数字说明有重复的数字，然后让next指针下移一个数字，指向第三个数字，然后再判断current与next是否相等，如果相等，让next继续下移，直到curr指向的值不等于next指向的值，然后next-1对应的数字一定是重复的，然后让current=next，next=current+1，进入下一次循环判断。如果是连续的两个数字比如current指向第5个数字是4，next指向第6个数字是5，此时虽然next指向的值不等于current指向的值，但显然没有重复的值，所以还应该加个判断如果他们相邻且不相等，让他们两个指针都下移，然后进入下一次循环判断。算法介绍得差不多了，下来咱就让代码说话吧。

快速排序算法：参考了数据结构(c语言版)  严蔚敏 吴伟民 编著 清华大学出版社

#include "iostream"
    using namespace std;
    
    int Partition(int array[], int low, int high)
    {
    	int pivotkey = array[low];
    
    	while (low < high)
    	{
    		while ((low < high) && (array[high] >= pivotkey))
    		{
    			high--;
    		}
    		array[low] = array[high];
    
    		while ((low < high) && (array[low] <= pivotkey))
    		{
    			low++;
    		}
    		array[high] = array[low];
    	}
    
    	array[low] = pivotkey;
    	return low;
    }
    
    void QuickSort(int array[], int low, int high)
    {
    	if (low < high)
    	{
    		int pivot = Partition(array, low, high);
    		QuickSort(array, low, pivot-1);
    		QuickSort(array, pivot+1, high);
    	}
    }
    
    void FindDifferentNum(int array[], int lenthOfArray)
    {
    	int current = 0;
    	int next = 1;
    	
    	for (int i=0; i<lenthOfArray-1; i++)
    	{
    		if (array[current] == array[next])
    		{
    			next++;
    			continue;
    		}
    		else if (next-current > 1) // 两个数字不相等而且不相邻，那么array[current]==array[next-1]
    		{                          // 所以把array[next-1]打印出
    			cout << array[next-1] << "  ";
    			current = next;
    			next++;
    		}
    		else // 两个数字不相等而且相邻的情况
    		{
    			current = next;
    			next++;
    		}
    	}
    	
    	if (current != lenthOfArray-1) 
    	{
    		cout << array[current] << endl;
    	}
    	
    }
    
    
    
    
    void main(){
    	int array[10] = {3, 3, 2, 1, 9, 9, 6, 5, 10, 10};
    	cout << "数组中的原始数字是：" << endl;
    	for (int i=0; i<10; i++)
    	{
    		cout << array[i] << "  ";
    	}
    	cout << endl;
    
    	QuickSort(array, 0, 9);
    
    	cout << "排序后的结果是：" << endl;
    	for (i=0; i<10; i++)
    	{
    		cout << array[i] << "  ";
    	}
    	cout << endl;
    
    	cout << "数组中重复的数字是" << endl;
    	FindDifferentNum(array, sizeof(array)/sizeof(int));	
    }

![1351350954_9634.jpg][]

[1351350954_9634.jpg]: https://img-my.csdn.net/uploads/201210/27/1351350954_9634.jpg