佛山做网站需要多少钱,抖音开放平台橡塑app,南宁seo外包服务,建设银行四川分行网站一.题目描述
在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 算法1.排序,然后遍历,时间复杂度O(nlogn),空…
一.题目描述
在一个长度为 n 的数组 nums 里的所有数字都在 0n-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; i1 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;
}本篇完
