一道不起眼面试题，但被头条面试官玩出花，48张图还原面试现场
牛客网题霸系列
小夕是牛客网题霸题解系列合作人员，删帖大大请手下留情 题目出自牛客题霸
考过这道题目的公司: 百度、腾讯、头条
漫画题解
题目：
来源：https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&&tqId=11203&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是一个重复的数字2。
返回描述：
如果数组中有重复的数字，函数返回true，否则返回false。
如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）
Java
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num))
return num;
}
return -1;
}C++
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_map<int, bool> 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的范围内。 数组中没有数字是重复的， 例如，如果输入长度为7的数组{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<int>& nums) {
for(int i = 0; i < nums.size(); ++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 NoneJS
var findRepeatNumber = function(nums) {
const length = nums.length;
for (let i = 0; i < length; ++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;
}
}
最后
原文带有视频讲解，目前牛客网不支持加入视频，想看视频的朋友可以看一下原文： 带视频的这道题题解原文
觉得文章不错的，不妨关注一下小夕的个人原创动漫算法题解的公众号【小夕学算法】，另外小夕也在组织每天刷一道算法题的活动，感兴趣的可以加小夕微信 teihanhan12342 一起每天刷一道算法题。
二维码图片会被牛客网手机端吞掉，可以点一下这里：小夕学算法 公众号二维码