剑指offer--数组中重复的数字

一.题目描述

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

算法1.排序,然后遍历,时间复杂度O(nlogn),空间O(logn)

int Cmp_int(const void* vp1, const void* vp2)
{return *(int*)vp1 - *(int*)vp2;
}
int findRepeatNumber1(int* nums, int numsSize)
{qsort(nums,numsSize,sizeof(int),Cmp_int);//调用排序算法,需要引用stdlib.hfor (int i = 0; i+1 < numsSize; i++){if (nums[i] == nums[i + 1])return nums[i];}return -1;
}

算法2:利用哈希表,时间O(n),空间O(n)

int findRepeatNumber(int* nums, int numsSize)
{int* arr = (int*)malloc(numsSize * sizeof(int));int i;int m;for (i = 0; i < numsSize; i++)arr[i] = -1;//-1表示无效值for (i = 0; i < numsSize; i++){m = nums[i];if (arr[m] != -1)//找到了{free(arr);return m;}arr[m] = m;}free(arr);return -1;//没有重复的
}

算法3.数据归位(把m存放到nums[m]位置)

int findRepeatNumber3(int* nums, int numsSize) //O(n),O(1){int m; for (int i = 0; i < numsSize; i++) {while (nums[i] != i)//当前位置,存放的不是当前数据,交换 {m = nums[i]; if (m == nums[m])//找到了 return m; nums[i] = nums[m]; nums[m] = m; }}return -1; 
}int main() 
{int nums[] = { 2, 3, 1, 0, 2, 5, 3 }; printf("%d\n", findRepeatNumber(nums,sizeof(nums)/sizeof(nums[0])));return  0; 
}

本篇完！