Leetcode---剑指Offer题3---数组中重复的数字

目录

• 1、介绍
• 2、题解

剑指Offer-面试题4---二维数组中的查找

1、介绍

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

找出数组中重复的数字。

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

这题的解法并不难，主要考查和面试官的沟通能力，一定要问面试官需要的时间/空间需求！！！

比如要空间O(1)，就不能用别的数据结构。

比如不能修改源数组。

2、题解

这里使用时间O(n)，空间O(1)的解法。

如果数组值和下标不相同，就交换到相同的下标，如果交换时和要交换的下标值相同，就是有重复的元素了。

        public int FindRepeatNumber(int[] nums)
        {
            if (nums == null || nums.Length<=1)
                return -1;

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != i)
                {
                    if (nums[i] == nums[nums[i]])
                        return nums[i];

                    int temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                    i--;
                }
            }
            return -1;
        }