《剑指offer》刷题系列01--数组中重复的数字

题目描述

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

思路分析

通过阅读提干，不难发现，题目要求是从已知数组中找到重复元素即可。这里列出三种解题思路仅作参考。

1）最容易想到的算法自然是先排序后通过依次遍历并与后一个元素相比较找出第一个重复元素即可。
2）利用数据结构--hash结构，依次遍历数组中每一个元素，同时将元素放入hash中，在放入前先做判断：如果在hash存在则说明找到重复元素，否则放入hash中，直到遍历完所有元素为止。
3）充分利用已知条件“数组里的所有数字都在0到n-1的范围内”，通过交换元素位置比较可以发现是否有重复元素。

代码部分

package com.team.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，
 * 但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
 *
 * @author zhangbocheng
 * @version v1.0
 * @date 2020/3/16 20:45
 */
public class DuplicateNumber {
    public static void main(String[] args) {
        DuplicateNumber dn = new DuplicateNumber();
        int[] array = {2,3,1,0,2,5,3};
        int[] duplication = new int[array.length];
        boolean result;
        System.out.printf("原始数组为：");
        for (int item: array) {
            System.out.printf("%d ", item);
        }

        result = dn.duplicateSort(array, array.length, duplication);
        if (result) {
            System.out.println("\n数组中第一个重复的数字为（排序法）：" + duplication[0]);
        } else {
            System.out.println("数组中第一个重复的数字为（排序法）：无重复数字！");
        }

        result = dn.duplicateHash(array, array.length, duplication);
        if (result) {
            System.out.println("数组中第一个重复的数字为（Hash）：" + duplication[0]);
        } else {
            System.out.println("数组中第一个重复的数字为（Hash）：无重复数字！");
        }

        result = dn.duplicate(array, array.length, duplication);
        if (result) {
            System.out.println("数组中第一个重复的数字为（移位法）：" + duplication[0]);
        } else {
            System.out.println("数组中第一个重复的数字为（移位法）：无重复数字！");
        }
    }

    /**
     * 方法一：排序法
     * @param numbers 待处理数组
     * @param length 待处理数组长度
     * @param duplication 保存结果的数组
     * @return 是否找到重复数字
     */
    private boolean duplicateSort(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length < 1) {
            return false;
        }

        quickSort(numbers, 0, numbers.length - 1);
        for (int i = 0; i < numbers.length-1; i++) {
            if (numbers[i] == numbers[i + 1]) {
                duplication[0] = numbers[i];
                return true;
            }
        }

        return false;
    }

    private void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pos = partition(array, low, high);
            quickSort(array, low, pos - 1);
            quickSort(array, pos + 1, high);
        }
    }

    private int partition(int[] array, int low, int high) {
        int key = array[low];
        while (low < high) {
            while (low < high && array[high] >= key) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= key) {
                low++;
            }
            array[high] = array[low];
        }

        array[low] = key;
        return low;
    }

    /**
     * 方法二：Hash法
     * @param numbers 待处理数组
     * @param length 待处理数组长度
     * @param duplication 保存结果的数组
     * @return 是否找到重复数字
     */
    private boolean duplicateHash(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length < 1) {
            return false;
        }

        Map<Integer, Integer> map = new HashMap<>(16);
        for (int item: numbers) {
            if (map.keySet().contains(item)) {
                duplication[0] = item;
                return true;
            }

            map.put(item, 1);
        }

        return false;
    }

    /**
     * 方法三：移位法
     * @param numbers 待处理数组
     * @param length 待处理数组长度
     * @param duplication 保存结果的数组
     * @return 是否找到重复数字
     */
    private boolean duplicate(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length < 1) {
            return false;
        }

        for (int number: numbers) {
            if (number < 0 || number >= length) {
                return false;
            }
        }

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

                temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }

        return false;
    }
}