剑指offer03:数组中重复的数字

题目

题目链接

剑指Offer:数组中重复的数字

题目描述

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

分析

首先本题要清楚题目的要求:

  • 先对数组进行排序,然后再查找排序后的数组中的重复元素
public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            return false;
        }
        Arrays.sort(numbers);
        for (int i = 0; i < length - 1; i++) {
            if (numbers[i + 1] == numbers[i]) {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}
  • 从头到尾依次扫描数组中每一个数字。当扫描到第i个元素时,比较该位置数值m是否等于i。若是,接着扫描下一个数字;否则,将其与第m个数字进行比较。若相等,则返回该重复数字;否则,交换两个数字,继续重复前面的过程。

    数组的长度为 n 且所有数字都在 0 到 n-1 的范围内,我们可以将每次遇到的数进行"归位",当某个数发现自己的"位置"被相同的数占了,则出现重复。
    扫描整个数组,当扫描到下标为 i 的数字时,首先比较该数字(m)是否等于 i,如果是,则接着扫描下一个数字;如果不是,则拿 m 与第 m 个数比较。如果 m 与第 m 个数相等,则说明出现重复了;如果 m 与第 m 个数不相等,则将 m 与第 m 个数交换,将 m "归位",再重复比较交换的过程,直到发现重复的数

    举个栗子:
    以数组 {2,3,1,0,2,5,3} 为例
    当 i = 0 时,nums[i] = 2 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{1,3,2,0,2,5,3}
    此时 i = 0,nums[i] = 1 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{3,1,2,0,2,5,3}
    此时 i = 0,nums[i] = 3 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{0,1,2,3,2,5,3}
    此时 i = 0,nums[i] = 0 = i,继续下一组
    当 i = 1,nums[i] = 1 = i,继续下一组
    当 i = 2,nums[i] = 2 = i,继续下一组
    当 i = 3,nums[i] = 3 = i,继续下一组
    当 i = 4,nums[i] = 2 != i,判断 nums[i] 等于 nums[nums[i]],出现重复,赋值返回

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            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;
                }
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            }
        }
        return false;
    }
}
  • 利用 HashSet或辅助数组 解决,从头到尾扫描数组,每次扫描到一个数,判断当前数是否存在 HashSet 中,如果存在,则重复,对 duplication 赋值返回,否则将该数加入到 HashSet 中。
public class Solution {
    //利用 HashSet 解决,从头到尾扫描数组,每次扫描到一个数,判断当前数是否存在 HashSet 中,如果存在,
    //则重复,对 duplication 赋值返回,否则将该数加入到 HashSet 中
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            return false;
        }
        Set set = new HashSet();
        for (int i = 0; i < numbers.length; i++) {
            if (set.contains(numbers[i])) {
                duplication[0] = numbers[i];
                return true;
            }else {
                set.add(numbers[i]);
            }
        }
        return false;
    }
}

扩展:

在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。从数组中找出任意一个重复的数字,但不能修改输入的数组。如{2,3,5,4,3,2,6,7}得到2或者3.

  • 在数字 1~n 中取中间值 m = (1+n) / 2, 此时数字包括 1~m, m+1~n 两段;
    遍历数组,获得数字 1~m 的个数;
    如果数字 1~m 的个数大于 m,说明 1~m 这一段内肯定有重复数字,那么在这一段内继续取中间值比较;
    如果数字 1~m 的个数等于 m,这一段不一定有重复数字,比较后一段;
    如果数字 1~m 的个数小于 m,说明 m+1~n 这一段一定有重复数字,在后一段取中间值比较;
    按照上述方法一直取中间值比较,直到只剩一个数字且这个数字出现次数超过 1 ,该数字即为重复数字
public class Other {
    /**
     * 
     * 1)把1~n的数字从中间的数字m分为两部分,前面一半为1~m,后面一半为m+1~n
     *
     * 2)如果1~m这部分的数字对应数组里的值超过m个,这个区间就包含有重复的数字,否则就是另外一个区间包含重复的数字。就算两个区间都有重复的也只要再对某一个区间进行二分,因为题目要求只要找到任意一个重复的数字
     *
     * 3)继续把重复数字的区间进行二分,直到找到一个重复的数字
     */
    /**
     * int mid = (start+end)/2可能会溢出,用>>是遇到负奇数的时候求上下界统一
     * -5/2=-2   5/2=2   上下界求法不统一
     * -5>>1=-3  5>>1=2  统一
     */
    int getDuplication(int[] numbers, int length) {

        int start = 1;
        int end = length - 1;
        while (end >= start) {

            int mid = start + (end - start) >> 1;
            int count = countRange(numbers, length, start, mid);
            if (end == start) {
                if (count > 1) {
                    return start;
                }
                break;
            }
            if (count > (mid - start + 1)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    int countRange(int[] numbers, int length, int start, int end) {
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (numbers[i] >= start && numbers[i] <= end) {
                ++count;
            }
        }
        return count;
    }
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议