一道不起眼的面试题被玩出了花 linpxing-liwei-博客世家

浏览次数: 843

来源 | 小夕学算法

作者 | 小夕

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

Java

    public int findRepeatNumber(int[] nums) {
        Set set = new HashSet();
for (int num : nums) {
if (!set.add(num))
return num;
        }
return -1;
    }

C++

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        unordered_map map;
for(int num : nums) {
if(map[num]) return num;
            map[num] = true;
        }
return -1;
    }
};

JS

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
let s=new Set();
for(var i in nums){
        var Length=s.size;
        s.add(nums[i]);
if(s.size==Length)
return nums[i];
    }
};

Python

class Solution(object):
    def findRepeatNumber(self, nums):
"""
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
for i in nums:
if i not in dic:
                dic[i] = 0
else:
return i

新题目：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中没有数字是重复的。例如，输入数组{2,1,3,0,4}，要把该数组重新排好序。要求不能使用语言自带的排序算法，且空间复杂度为O(1)。

题目思路

数组中的元素值是2、1、3、0、4，同时数组的索引下标是0、1、2、3、4。
可以发现数组的元素的索引和数组值存在一一对应的关系。
因此可以通过遍历数组，比如某第一个元素值2索引是0，我们做一个交换，就把它放到nums[2]中（也就是到把第一个元素值2放到了索引是2的地方，即nums[current] = current），这样把数组的值和索引一一对应起来。

新题目图解思路

动画视频：

新题目复杂度

动画视频

代码实现

Java

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int current = 0;current < nums.length;) {
            if (nums[current] == current) {
                current++;
            } else {
                // 当前index = current下标值nums[current]和 index = nums[current] 的下标值 nums[nums[current]]相等
                if(nums[current] == nums[nums[current]]) {
                    return nums[current];
                } else {
                    swapTwoNumberInArray(nums, current, nums[current]);
                }
            }
        }
        return -1; // 没找到
    }
    public  void swapTwoNumberInArray(int[] nums, int current, int another) {
        int temp = nums[current];
        nums[current] = nums[another];
        nums[another] = temp;
    }
}

C++

class Solution {
public:
    int findRepeatNumber(vector& nums) {
for(int i = 0; i         {
while(nums[i] != i)     //当前元素不等于下标
            {
if(nums[i] == nums[nums[i]])    return nums[i];
                swap(nums[i],nums[nums[i]]);            
            }
        }   
return -1;
    }
};

Python

class Solution(object):
    def findRepeatNumber(self, nums):
"""
        :type nums: List[int]
        :rtype: int
        """
for i in range(len(nums)):
while nums[i] != i:
if nums[nums[i]] == nums[i]:
return nums[i]
                nums[nums[i]] , nums[i] = nums[i] , nums[nums[i]] # 交换
return None

JS

var findRepeatNumber = function(nums) {
    const length = nums.length;
for (let i = 0; i         // 检测下标为i的元素是否放在了位置i上
while ((num = nums[i]) !== i) {
if (num === nums[num]) {
return num;
            }
            [nums[i], nums[num]] = [nums[num], nums[i]]; // 交换
        }
    }
};

小夕的牛客网Java代码

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public  boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null) {
            return false;
        }
        if(findRepeatNumber(numbers) != -1){
            duplication[0] = findRepeatNumber(numbers);
            return true;
        }
        return false;
    }
    public  int findRepeatNumber(int[] nums) {
        for(int current = 0;current < nums.length;) {
            // num[current] = current 说明归位了 也就是成为了有序数组，那么继续往下遍历。
            if (nums[current] == current) {
                current++;
            } else {
                // 当前index = current下标值nums[current]和 index = nums[current] 的下标值 nums[nums[current]]相等
                // 找到重复数字了
                if(nums[current] == nums[nums[current]]) {
                    return nums[current];
                } else {
                    // 没找到重复数字 所以把这两个数组中的数进行交换
                    // 目的是为了让num[current] = current 这样就变成了有序数组
                    swapTwoNumberInArray(nums, current, nums[current]);
                }
            }
        }
        return -1; // 没找到
    }
    public  void swapTwoNumberInArray(int[] nums, int current, int another) {
        int temp = nums[current];
        nums[current] = nums[another];
        nums[another] = temp;
    }
}

第一个数字的思路

还是复用之前的思路，把数字依次归位。
当找到重复的数字的时候，不直接返回，而是用set把所有的重复数字保留下来。
然后遍历数组，找到这些重复数字的下标，然后把下标最小的那个数字返回，就得到了第一个了。

第一个数字AC的牛客网Java代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public  boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null) {
            return false;
        }
        Set<Integer> repeatNumberSet = new HashSet<>();
        Map<Integer, Integer> repeatNumberMap =  new HashMap<>();
        getMap(numbers, repeatNumberMap);
        findRepeatNumber(numbers, repeatNumberSet);
        if(repeatNumberSet.size() != 0){
            duplication[0] = getFirstNumber(numbers, repeatNumberSet, repeatNumberMap );
            return true;
        }
        return false;
    }
    public  int findRepeatNumber(int[] nums, Set<Integer> repeatNumberSet) {
        for(int current = 0;current < nums.length;) {
            // num[current] = current 说明归位了 也就是成为了有序数组，那么继续往下遍历。
            if (nums[current] == current) {
                current++;
            } else {
                // 当前index = current下标值nums[current]和 index = nums[current] 的下标值 nums[nums[current]]相等
                // 找到重复数字了
                if(nums[current] == nums[nums[current]]) {
                    repeatNumberSet.add(nums[current]);
                    current++;
//                    return nums[current];
                } else {
                    // 没找到重复数字 所以把这两个数组中的数进行交换
                    // 目的是为了让num[current] = current 这样就变成了有序数组
                    swapTwoNumberInArray(nums, current, nums[current]);
                }
            }
        }
        return -1; // 没找到
    }
    public  void swapTwoNumberInArray(int[] nums, int current, int another) {
        int temp = nums[current];
        nums[current] = nums[another];
        nums[another] = temp;
    }
    public  void getMap(int[] nums,  Map<Integer, Integer> repeatNumberMap) {
        for(int i = 0;i < nums.length; i++) {
            Set<Integer> keySet = repeatNumberMap.keySet();
            if (keySet != null && keySet.contains(nums[i])) {
                if (repeatNumberMap.get(nums[i]) > i) {
                    repeatNumberMap.put(nums[i],i);
                }
            } else {
                repeatNumberMap.put(nums[i],i);
            }
        }
    }
    public  int getFirstNumber(int[] nums, Set<Integer> repeatNumberSet, Map<Integer, Integer> repeatNumberMap) {
        int minIndex = nums.length;
        int min = -1;
        for(Integer repeatNumber : repeatNumberSet ) {
            if (repeatNumberMap.get(repeatNumber) < minIndex) {
                minIndex = repeatNumberMap.get(repeatNumber);
                min = repeatNumber;
            }
        }
        return min;
    }
}