提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【C剑指offer】03数组中的重复元素

数组 排序
2023-02-25 18:20:21 时间

每一个不曾起舞的日子,都是对生命的辜负

对现阶段的我来嗦,这个第三种方法着实有点难理解,想了好久才相通,而且好多细节问题!!!

文章目录

问题描述

总体分析:只用找出任何一个重复的数字,找到返回该值,找不到返回-1,也可以返回其他值,但是绝对不要返回0到n-1这些数,否则与重复的数值可能重复…

方法一：排序比较

最简单的思路:先对数组排序,排完序后重复的元素肯定挨着,前后两两两比较即可

主函数

int main()
{
	int arr[5] = { 1,2,3,4,3 };
	int n = sizeof(arr) / sizeof(arr[0]);
	//使用（插入法）排序
	Array_sort(arr, n);
    //打印出排序后的数组（检验排序是否成功）
	Print_array(arr, n);
    //ret接收返回值
	int ret=Search_array(arr, n);
	if (ret !=-1)
	{
		printf("找到了,最少有一个是%d", ret);
	}
	else
	{
		printf("没找到");
	}
	
	return 0;
}

插入排序:

void Array_sort(int* a, int n)
{
	for (int i = 0; i <n-1; i++)
	{
		int end = i;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp<a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
	
}

打印

void Print_array(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d\t", arr[i]);
	}
}

查找

int  Search_array(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		if (arr[i] == arr[i + 1])
			return arr[i];
	}
	return -1;
}

方法二:临时数组

malloc一个临时数组temp[] (记得初始化位0),将数组arr[]的值和temp的下标一一对应(映射)起来,例如arr的某一个元素是4,那么就把temp[4]这个数组从0变成1,直到temp数组的某一个元素值为2时说明加了两次1,也就是快找到重复的元素了,这个元素就是此时temp的下标,也就是array[i].

int Search_array(int array[], int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		temp[i] = 0;
	}
	for (int i = 0; i < n; i++)
	{
		temp[array[i]]++;
		if (temp[array[i]] == 2)return array[i];
	}
 return 0;
}

方法三：原地哈希

把元素放到指定位置:原地哈希,有点难以描述,建议举例推演 

int Search_array(int* a, int n)
{
	int i = 0;
	while (i<n)
	{
	    // 循环遍历，当前遍历值(a[i])和其索引值(i)一致时，i自增，查看下一位
		if (a[i] == i)
		{
			i++;
			continue;
		}
		// 跳出循环的条件，当前遍历值(a[i])与以该值为索引得到(a[a[i]])的数组值相同时，表明该值是重复的。
		else
		{
			if (a[i] == a[a[i]])
			{
				return a[i];
			}
			else
			{
			/*	int temp = a[i];
				a[i] = a[a[i]];//此处a[i]已经发生变化,这关联下一行的a[i]
				a[a[i]] = temp;*/错误

            // 反复交换，直到遍历值与索引值一致时，改变i值
				int temp = a[a[i]];
				a[a[i]] = a[i];
				a[i] = temp;//正确
				//或者将写成:
				//int temp=a[i];
				//a[i]=a[temp];
				//a[temp]=temp;//正确
            
			}
		}
	}
	return -1;// 并未找到相同值，返回-1
}

相关文章