剑指offer系列——剑指 Offer 03. 数组中重复的数字(C语言)

⭐️前面的话⭐️

大家好！博主开辟了一个新的专栏——剑指offer，我要开始刷题了！这个专栏会介绍《剑指offer》书上所有的面试编程题。并且会分享一些我的刷题心得。由于博主水平有限，如有错误，欢迎指正，如果有更好的解题思路和算法可以分享给博主哦！一起加油！一起努力！

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆华为云首发时间：🌴2022年4月30日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《C语言程序设计》📚《剑指offer》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

:star:剑指 Offer 03. 数组中重复的数字:star:

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

:bulb:示例：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

:bulb:限制：

2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
:star:解题思路:star:
根据题意，数组有n个元素，数组元素的范围为0~n-1，如果数组中没有重复的元素，对数组进行排序后对应下标为i的元素为i，但是数组中是存在重复数字的，所以有些位置对应多个元素，有些位置则没有元素。
所以我们可以根据将数组下标与其对应的数组元素进行比较，如果相等则跳过，接着比较后面一个数组下标与其对应数组元素比较，最多遍历完整个数组。如果不相等则将该元素与以该元素为下标所对应的数组元素进行比较，相等就表示找到了一个重复的元素，返回该元素的值，不相等则将这两个元素交换。
时间复杂度：最坏遍历完数组，时间复杂度为O(N)。
空间复杂度：没有开辟新空间，空间复杂度O(1)。

编程语言：C语言
在线编程平台：力扣

int findRepeatNumber(int* nums, int numsSize){
    if (nums == NULL || numsSize <=0)
    {
        return -1;
    }
    int i = 0;
    while(i < numsSize)
    {
        if (*(nums + i) < 0)
        {
            return -1;
        }
        if (*(nums + i) == i)
        {
            i++;//如果数组下标与该下标对应的数（记为m）相等，i指向下一位，否则进行比较该数m与数组下标为m的数是否相等
            continue;
        }
        else
        {
            int m = *(nums + i);
            if (*(nums + i) == *(nums + m))
            {
                return *(nums + i);//如果相等，则找到重复数字
            }
            else
            {
                *(nums + i) = *(nums + m);//如果不相等，将数组下标为i对应的数（数字m）与下标为m对应的数交换
                *(nums + m) = m;
            }
        }
    }
    return -1;
}