栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构和算法】LeetCode,初级算法-4存在重复元素

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构和算法】LeetCode,初级算法-4存在重复元素

截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

视频分析

LeetCode,初级算法-存在重复元素


代码部分

1,暴力破解

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

2,排序

    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int ind = 1; ind < nums.length; ind++) {
            if (nums[ind] == nums[ind - 1]) {
                return true;
            }
        }
        return false;
    }

3,使用HashSet

    public boolean containsDuplicate(int[] nums) {
        Set set = new HashSet<>();
        for (int num : nums) {
            //因为集合set中不能有重复的元素,如果有重复的
            //元素添加,就会添加失败
            if (!set.add(num))
                return true;
        }
        return false;
    }

4,位运算

    public boolean containsDuplicate(int[] nums) {
        //找出数组中的最大值和最小值
        int min = nums[0];
        int max = min;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        //计算数组中最大值和最小值的差值,目的是要确定位图的长度
        int distant = max - min + 1;
        long[] bitmap = new long[(distant - 1) / 64 + 1];
        for (int num : nums) {
            //根据当前数字到最小数字的长度,定位到当前数字在位图
            //中的位置。判断这个位置是不是1,如果是1,说明存在
            //重复的数字
            int tmp = num - min;
            if ((bitmap[tmp / 64] & (1L << (tmp % 64))) != 0)
                return true;
            //如果不存在重复的数字,就把当前这个位置变为1
            bitmap[tmp / 64] |= 1L << (tmp % 64);
        }
        return false;
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/967476.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号