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

217. 存在重复

程序员文章站 2023-12-27 18:23:39
...

217. 存在重复

给定一个整数数组,判断是否存在重复元素。

如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

思路分析:

  1. 考虑数组是否有序
  2. 有序情况下只需遍历数组依次比较相邻两个数是否存在相等的情况
  3. 无序情况下,可以先排序然而按照步骤2进行处理,也可以直接逐个遍历元素查找是否存在其他相同的元素
  4. 利用集合不能存在相同元素的原理

方案一:直接比较,时间复杂度 O(n2)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) {
            return false;
        }
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[i] == nums[j]) {
                    return true;
                } 
            }
        } 
    
       return false;
} 

方案二:先排序后比较,快排 O(nlogn)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) {
            return false;
        }
        
        quickSort(nums, 0, nums.length - 1);

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return true;
            }
        }

       return false;
    }

    // 快排算法,快排每次选取一个任意数据(一般选首部元素)作为关键数据,
    // 一次遍历完成后都能把数据分成两部分,在其左边的都比它小,在其右边的都比它大
    private void quickSort (int[] nums, int start, int end) {
        
        if (start < end) {
            int separatorIndex = searchSeparatorIndex(nums, start, end);
            quickSort(nums, start, separatorIndex - 1);
            quickSort(nums, separatorIndex + 1, end);
        }
    }
    
    // 一趟快速排序过程             
    // 1. 设置这趟快排的开始位置 start,结束位置 end 和关键数据 keyNum       
    // 2. 从 end 开始向前遍历(end--),找到第一个小于 keyNum 的元素时,将 nums[end] 赋值给 nums[start] ,并将start++         
    // 3. 从 start 开始向后遍历(start++),找到第一个大于 keyNum 的元素时,将 nums[start] 赋值给 nums[end] ,并将end--   
    // 4. 重复2,3操作,直到 start == end 循环结束  
    // 5. 将 keyNum 赋值给 nums[start],此时 start 值就是分割位置,在其左边的都比它小,在其右边的都比它大
    // 对 start 位置的左右两部分区间分别递归调用一趟快速排序过程
    private int searchSeparatorIndex (int[] nums, int start, int end) {
        int keyNum = nums[start];
        
        while (start < end) {
            while (start < end && keyNum < nums[end]) {
                end--;
            }
            
            if (start < end) {
                nums[start++] = nums[end];
            }
            
            while (start < end && keyNum > nums[start]) {
                start++;
            }
            
            if (start < end) {
                nums[end--] = nums[start];
            }
            
        }
        
        nums[start] = keyNum;
        
        return start;
    }
} 

方案三:利用集合不能添加重复元素原理

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) {
            return false;
        }
        
        Set<Integer> set = new HashSet<>();
        int index = 0;
        while(index < nums.length) {
            if (!set.add(nums[i])) {
                return true;
            }
        }

    return false;

    }
}

方案四:先排序后比较,使用 Arrays.sort() 进行排序

Arrays.sort() 方法按照策略实现了归并插入排序和优化后的快排,比普通快排更快

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) {
            return false;
        } 

        Arrays.sort(nums);

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return true;
            }
        }

     return false;
    }
}

方案五:在原有方案一的基础上进行优化,边比较相邻元素边进行位置调整,减少遍历次数

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 2) {
            return false;
        } 

        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j] && j+1 != i) {
                    int temp = nums[i];
                    nums[i] = nums[j+1];
                    nums[j+1] = temp;
                    break;
                }
                if(nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
}

作者:石先
链接:https://www.jianshu.com/p/ef4aca5a11e4
来源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

相关标签: 存在重复元素

上一篇:

下一篇: