剑指offer----C语言版----第一天
目录
1. 数组中重复的数字Ⅰ
1.1 题目描述
1.2 思路一
1.3 思路二
1.4 思路三（最优解）
1. 数组中重复的数字Ⅰ
原题：剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）
https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
1.1 题目描述
给你一个数组，大小为N，数组里面的值的介于 [ 0, N-1 ]，要求你找出数组中任意一个重复的数字。
1.2 思路一
我们选用一个时间复杂度为O(N*logN)的排序算法对数组进行排序，例如快速排序，堆排序，归并排序。然后再去遍历排序好的数组，找出重复的数字。解题的时间复杂度：O(N*logN)，空间复杂度：O(1)。
我这里自己写了快速排序的代码，如果大家嫌麻烦可以使用C语言的库函数qsort来对数组进行排序，底层逻辑也是快速排序，但是在数据量比较小的时候用的是插入排序，库函数嘛，效率的优化是最高的。
cplusplus.com - The C++ Resources Network
https://legacy.cplusplus.com/大家可以使用这个来查看C语言的标准库函数。
//数字交换
void Swap(int* pa, int* pb)
{
int temp =*pa;
*pa = *pb;
*pb = temp;
}
//快速排序优化算法：三数取中间
int GetMidIndex(int* arr, int left, int right)
{
int mid = (left + right) >> 1;
if (arr[mid] > arr[left])
{
if (arr[left] > arr[right])
{
return left;
}
else if (arr[mid] > arr[right])
{
return right;
}
else
{
return mid;
}
}
// arr[mid] < arr[left]
else
{
if (arr[right] > arr[left])
{
return left;
}
else if (arr[mid] > arr[right])
{
return mid;
}
else
{
return right;
}
}
}
void QuickSort(int* arr, int left,int right)
{
if (left >= right)
{
return;
}
int index = GetMidIndex(arr, left, right);
int begin = left;
int end = right;
Swap(&arr[index], &arr[begin]);
int pivot = begin;
int key = arr[begin];
while (begin < end)
{
//找小的
while (begin < end && arr[end] >= key)
{
--end;
}
arr[pivot] = arr[end];
pivot = end;
//找大的
while (begin < end && arr[begin] <= key)
{
++begin;
}
arr[pivot] = arr[begin];
pivot = begin;
}
pivot = begin;
arr[pivot] = key;
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int findRepeatNumber(int* nums, int numsSize){
assert(nums);
int left = 0;
int right = numsSize - 1;
QuickSort(nums, left, right);
int i = 0;
for(i = 0; i < numsSize - 1; i++)
{
if(nums[i] == nums[i + 1])
{
return nums[i];
}
}
return -1;
}
1.3 思路二
我们可以利用一个简单的哈希表：开辟一个同样大小的数组arr，并将数组arr初始化为0，然后遍历原来的数组nums，将nums数组的值对应到arr相应下标的位置，让他的值加一，如果再遍历过程中遇到arr的值大于1，则找到了该重复的数字。该解题方法的时间复杂度：O(N)，空间复杂度O(N)，以空间换时间。
int findRepeatNumber(int* nums, int numsSize){
int* arr = (int*)calloc(numsSize, sizeof(int));
int i = 0;
for(i = 0; i < numsSize; i++)
{
arr[nums[i]] += 1;
if(arr[nums[i]] > 1)
{
free(arr);
arr = NULL;
return nums[i];
}
}
free(arr);
arr = NULL;
return -1;
}
1.4 思路三（最优解）
我们分析题目可以得到如下规律：数组大小是N，数值范围是N-1，如果说该数组没有重复的元素，那么数组中每一个下标都可以对应与其下标相同的数字，如果说有重复的数字，那么，会出现一个下标有多个与其下标相等的数字，或者出现没有与其下标相等的数字。
利用这一特性，我们可以遍历该数组，扫描到下标 i 时，首先比较这个数 m 与下标 i 是否相等，如果相等，继续扫描下一个元素。如果不相等，将m与下标为 m 的数进行比较，如果相等则找到一个重复的数字，如果不相等将 m 交换到下标为 m 的位置，对交换过来的数字继续重复上述判断即可，直到找到重复的数字。
解题的时间复杂度：O(N)，空间复杂度O(1)。
下面以一组例子来演示方便理解：
void Swap(int* pa, int* pb)
{
int temp = *pa;
*pa = *pb;
*pb = temp;
}
int findRepeatNumber(int* nums, int numsSize){
int i=0;
for(i = 0; i < numsSize; i++)
{
while(nums[i] != i)
{
if(nums[i] == nums[nums[i]])
{
return nums[i];
}
Swap(&nums[i],&nums[nums[i]]);
}
}
return -1;
} 