首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer(一):找出数组中重复的数字

剑指offer(一):找出数组中重复的数字

作者头像
程序员小浩
发布2020-08-04 16:04:12
5960
发布2020-08-04 16:04:12
举报
文章被收录于专栏:小浩算法小浩算法

❝涓滴之水终可以磨损大石,不是由于它力量强大,而是由于昼夜不舍的滴坠。——贝多芬❞

找出数组中重复的数字

题目描述

在一个长度为 n 的数组里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},那么对应的输出是重复的数字 2 或者 3

解法

解法一

排序后,顺序扫描,判断是否有重复,时间复杂度为 O(n²)

解法二

利用哈希表,遍历数组,如果哈希表中没有该元素,则存入哈希表中,否则返回重复的元素。时间复杂度为 O(n),空间复杂度为 O(n)

解法三

长度为 n,元素的数值范围也为 n,如果没有重复元素,那么数组每个下标对应的值与下标相等。

从头到尾遍历数组,当扫描到下标 i 的数字 nums[i]

  • 如果等于 i,继续向下扫描;
  • 如果不等于 i,拿它与第 nums[i] 个数进行比较,如果相等,说明有重复值,返回 nums[i]。如果不相等,就把第 i 个数 和第 nums[i] 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 O(n),因为每个元素最多只要两次交换,就能确定位置。空间复杂度为 O(1)


/**
 * @author bingo
 * @since 2018/10/27
 */

public class Solution {
    /**
     * 查找数组中的重复元素
     * @param numbers 数组
     * @param length 数组长度
     * @param duplication duplication[0]存储重复元素
     * @return boolean
     */
    public boolean duplicate(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length < 1) {
            return false;
        }
        for (int e : numbers) {
            if (e >= length) {
                return false;
            }
        }

        for (int i = 0; i < length; ++i) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                swap(numbers, i, numbers[i]);
            }
        }

        return false;
    }

    private void swap(int[] numbers, int i, int j) {
        int t = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = t;
    }
}

测试用例

  1. 长度为 n 的数组中包含一个或多个重复的数字;
  2. 数组中不包含重复的数字;
  3. 无效测试输入用例(输入空指针;长度为 n 的数组中包含 0~n-1 之外的数字)。

我把我写的所有题解整理成了一本电子书放在了 github 上,三天内冲击到 github 排行榜榜首!近 5w 人下载阅读!要获取的话,直接进入下方链接就可以了(记得给我点个 star):

https://github.com/geekxh/hello-algorithm

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-08-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小浩算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 找出数组中重复的数字
    • 题目描述
      • 解法
        • 解法一
        • 解法二
        • 解法三
      • 测试用例
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档