寻找数组中的重复数字

SPPan 2019-03-21 算法基础 135人已围观

问题描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

问题关键点

  • 所有数字都在 0 到 n-1 的范围内
  • 找出数组中任意一个重复

思路

使用最小的空间复杂度和时间复杂度来处理。

由于所有数字都在0到n-1之间,证明数组的长度一定大于最大一个数,可以考虑把所有的数按照自己的值放入到数组对应的位置,如果放入的位置已经存在内容,证明该数字存在重复。

只需要找出其中任意一个重复的数字,则可以在第一次发现重复数字的时候直接结束程序。

具体实现

public int duplicate(int[] nums, int length) throws Exception {
    if (nums == null || length <= 0)
        throw new Exception("nums not be null")
    for (int i = 0; i < length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            swap(nums, i, nums[i]);
        }
    }
    throw new Exception("not found")
}

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

吐槽(1)

文章评论

    共有1条评论

      2019-07-14 19:07 匿名网友

      <script>alert("文章写的不错!");</script>

文章目录