欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode面试题03. 数组中重复的数字

程序员文章站 2022-06-17 17:06:21
...

LeetCode面试题03. 数组中重复的数字

方法一:遍历数组
由于只需要找出数组中任意一个重复的数字,因此遍历数组,遇到重复的数字即返回。为了判断一个数字是否重复遇到,使用集合存储已经遇到的数字,如果遇到的一个数字已经在集合中,则当前的数字是重复数字。

LeetCode面试题03. 数组中重复的数字

public class Solution {
    public int FindRepeatNumber(int[] nums) {
        HashSet<int> map = new HashSet<int>();
        for(int i = 0; i < nums.Length; i++)
        {
            if(map.Contains(nums[i]))
                return nums[i];
            else
                map.Add(nums[i]);
        }
        return -1;
    }
}

方法二:类似交换排序
由于题目规定所有数字都在 0~n-1 的范围内,因此如果没有任何重复数字,数组从小到大排列后是下标为i的位置对应数字i。

可以判断i与数组中下标i位置的数字m是否相等,如果不相等,将下标i位置的数字m交换到数组中下标为m的位置。思想其实就是不断的遍历将无序的数组逐渐变成有序,如果中间遇到下标位置下标i位置的数字m与下标为m的位置数字相等,则得到最终结果。

时间复杂度:O(nlogn) (最坏情况下的排序)

空间复杂度:O(1)

public class Solution {
    public int FindRepeatNumber(int[] nums) {
        for(int i = 0; i < nums.Length; i++)
        {
            if(i != nums[i])
            {
                if(nums[nums[i]] != nums[i])
                    nums[nums[i]] = nums[i];
                else
                    return nums[i];
            }
        }
        return -1;
    }
}

 

 

 

 

相关标签: 算法 leetcode