美文网首页LeetCode
1507(442)-数组中重复的数字->数组中重复的数据

1507(442)-数组中重复的数字->数组中重复的数据

作者: 华雨欣 | 来源:发表于2020-03-26 15:40 被阅读0次

    这两道题题目基本一样,只不过一个只需要找到一个,一个需要找到所有的数字,难度稍稍大了一点,废话不多说直接上题。

    题目一

    这道题其实还是比较简单的,而且解决方法也很多样,这里我会列举几种常用的方法,并讲解一种比较巧妙的方法。

    核心思想

    • 暴力法
      既然要找重复的数字,那最直接的方法就是遍历每个元素,然后对每个元素向后继续遍历剩下的元素,找到重复的直接返回即可。时间复杂度O(N²)
    • 集合法
      我们可以使用一个集合(或者定义一个大数组,下标对应给定数组元素的值,然后0表示没有这个数,1表示出现过这个数即可)HashSet,然后遍历数组向集合中加入元素,如果contains的话返回即可。时间复杂度O(N),空间复杂度O(N)
    • 排序法
      既然要寻找重复元素,直接将数组排序,然后找到 nums[i] == nums[i + 1]直接返回即可。时间复杂度O(nlogn) 不过Java的快排在实际使用时效率可能会优于维护HashSet。

    这些就是比较常见而且容易想到的方法,接下来的方法可能不是很容易想到,是在集合法的基础上进行优化,由于集合法需要额外的O(N)的空间,可以对此进行优化。至于优化的方法,就是使用题目给的 nums数组,从而不需要使用额外的空间。因为题目给出了数组里的数字都限定在 0 — n - 1之间,那么我们可以让数字i 就存放在数组的 nums[i] 的位置上,详见代码。

    完整代码

    class Solution {
        public int findRepeatNumber(int[] nums) {
            for(int i = 0; i < nums.length; i++){
                while(nums[i] != i){
                    if(nums[i] == nums[nums[i]]){
                        //想要交换的数组元素重复
                        return nums[i];
                    }
                    int temp = nums[i];//备份nums[i];
                    nums[i] = nums[temp];//交换nums[nums[i]] 和nums[i]
                    nums[temp] = temp;
                }
            }
            return -1;
        }
    }
    

    对于每一个下标 i 都判断他的位置是否放了正确的数字 i ,是的话直接判断下一个下标,不是的话将nums[i] 交换到正确的位置然后依次循环,而如果他想要交换的元素已经出现过并且在正确位置了,就代表出现了重复,直接返回即可。时间复杂度O(N) 虽然使用了两层循环,但是依然是每个元素只访问一次,正确位置或者交换过到了正确位置的会直接跳过。 空间复杂度O(1) 除了题目给出的nums数组,没有使用额外的空间,是一个优解。

    题目二

    核心思路

    这道题跟上一题十分相似,但是细节上差了不少,这道题的数组限制元素的范围在1-n,也就是说还可以按上一题的交换方法,使得1在0处,2在1处……即可;再一个重复元素只会出现两次,并且要返回所有的重复元素,方法同样可以有多种,暴力、排序、集合都可以解决。不过题干给出一句“你可以不用到任何额外空间并在O(N)时间复杂度内解决这个问题吗?”,发现这个要求很苛刻,上边的三种方法都不能实现,而第一题的方法使用过了就不再赘述,我们尝试换一种方法,那该怎么解决呢?根据上一题的思路,我们需要在集合法的基础上将集合和给定的nums数组融到一起,以达到O(N)时间及无额外空间的要求。可以注意到题干给出的加粗字 两次 ,两次就是在引到我们到:-(-1)= 1,也就是说,我们仍然可以用数组的下标来代表元素,只不过这次我们不再用值,而是用符号,根据元素的范围,数组元素都是正整数,那只要对出现过的元素对应下标的元素符号改为 ‘-’ 就可以不使用额外的空间来解决问题。

    完整代码

    import java.util.ArrayList;
    import java.util.List;
    
    public class Solution {
    
        public List<Integer> findDuplicates(int[] nums) {
            ArrayList<Integer> ans = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[Math.abs(nums[i]) - 1] < 0) {
                    ans.add(Math.abs(nums[i]));
                } else {
                    nums[Math.abs(nums[i]) - 1] *= -1;
                }
            }
            return ans;
        }
    }
    

    如果数字nums[i] 出现过,那么它对应的下标元素 nums[nums[i]]就应该小于0,从而找到重复的元素。须要注意的是,因为当前遍历的nums[i]元素可能在之前被置为 -nums[i] 所以访问的时候要注意使用绝对值,不然会超出下标界限报错。这种方法还是很巧妙的,当然用上一题的交换方法也是可以AC的,看个人选择即可。

    相关文章

      网友评论

        本文标题:1507(442)-数组中重复的数字->数组中重复的数据

        本文链接:https://www.haomeiwen.com/subject/xblcuhtx.html