首页 > 一道不起眼面试题,但被头条面试官玩出花,48张图还原面试现场

一道不起眼面试题,但被头条面试官玩出花,48张图还原面试现场

牛客网题霸系列

小夕是牛客网题霸题解系列合作人员,删帖大大请手下留情 题目出自牛客题霸


题目链接:https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&&tqId=11203&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

考过这道题目的公司: 百度、腾讯、头条

漫画题解


题目:

来源: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 None

JS

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 一起每天刷一道算法题。
二维码图片会被牛客网手机端吞掉,可以点一下这里:小夕学算法 公众号二维码

更多模拟面试

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐