问题描述
总体分析:只用找出任何一个重复的数字,找到返回该值,找不到返回-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 }
