新鲜出炉的头条面试算法

Dear 丶 2022-05-10 14:22 203阅读 0赞

昨天下午实验室有一个同学参加了今日头条的面试，面试最终是以一个算法题结束。

题目如下：

给你一个有序整数数组，数组中的数可以是正数、负数、零，请实现一个函数，这个函数返回一个整数：返回这个数组所有数的平方值中有多少种不同的取值。举例：

1.  nums = \{-1,1,1,1\},
    
    那么你应该返回的是：1。因为这个数组所有数的平方取值都是1，只有一种取值
2.  nums = \{-1,0,1,2,3\}
    
    你应该返回4，因为nums数组所有元素的平方值一共4种取值：1,0,4,9

在往下看之前，请先进行思考，如果当时是你在面试，你会给出什么样的结题思路？下面会给出两种解法，最优解：时间复杂度：O(n)、空间复杂度O(1)。无论有没有思路，在往下看之前**一定要有自己的思考**。

第一种也是最为直接、简单的思路：把nums数组中所有数的绝对值，全部计算完之后再统计有多少种不同的取值。

**实现代码如下：**

public int handle(int[] nums) {
        if(nums==null  || nums.length==0)
            return 0;
        HashSet<Integer> set = new HashSet<Integer>();
        for (int number : nums)
            set.add(Math.abs(number));
        return set.size();
    }

上面的实现也很简单，主要是利用HashSet的去重特性，最后直接返回set的size。

但是呢，仅仅给出这种解法是过不了面试的，昨天面试的同学在面试结束之后才想到更优的解法，所以....当然这个同学已经拿到了很好的offer—网易。举这个案例只想和学弟学妹们在强调一遍：**算法的重要性。**

上面直接使用set的解法没有利用题目中**有序**条件，这也是优化的方向。

**那如何利用好有序这个条件呢？**

解思路法如下：

绝对值相等可能有哪些情况呢？

1.  两个同符号数的绝对值相等，这也意味着在有序数组中这个两个数是相邻的，这时只需要移动指针跳过相邻相等的数即可。
2.  两个异符号数的绝对值相等，所以我们需要维护两个指针，一个指针从前往后移动，一个从后往前移。原因是前面的负数绝对值可能与后面整数的绝对值相等，我们需要比较前后两个指针绝对值的大小。

综上，我们需要维护两个指针，i开始指向数组第一个元素，i=0；j开始指向数组最后一个元素，j = nums.length-1。i,j指针的另外含义是:数组中索引小于i和大于j的元素都已经被处理了；i，j指向的是未处理元素中绝对值最大的两个元素。当i>j的时候表明所有的元素都已经被处理了，循环结束。

**那么如何移动指针呢？**

1.  如果nums\[i\]与nums\[j\]的绝对值相等，此时执行i++，直到nums\[i\]的绝对值不等于nums\[j\]的绝对值（跳过相邻重复元素）；j也是做类似的移动，只不过j是向前移，j--；最后计数器加1。
2.  如果nums\[i\]的绝对值大于nums\[j\]的绝对值，我们移动指针i，并且计数器加1。原因？因为i和j指向未处理元素中绝对值最大的那个，nums\[i\]的绝对值已经是未处理元素中绝对值最大的两个数，也就是不可能存在一个未被处理的元素，它的绝对值与nums\[i\]的绝对值相等。所以这种情况下我们移动i指针。注意这里所说的移动指的是：执行i++直到nums\[i\]的绝对值发生了改变（跳过相邻相等的元素）。
3.  如果nums\[j\]的绝对值大，那么与上面类似，移动j指针。

具体代码实现如下：

public int handle (int[] nums) {
    
        if(nums==null  || nums.length==0)
            return 0;
    
        // result的缩写，最后的返回值
        int res = 0;
    
        //i是前指针；j是后指针   
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int num1=Math.abs(nums[i]);
            int num2=Math.abs(nums[j]);
            if (num1 > num2) {//移动i
                // 这两个数的绝对值不相等
                res += 1;
                while(i<=j && Math.abs(nums[i])==num1)
                    //过滤掉相邻的绝对值相等的数
                    i++;
            } else if (num1 < num2) {
                // 这两个数的绝对值不相等    
                res += 1;
                while(i<=j && Math.abs(nums[j])==num2)
                //过滤掉相邻的绝对值相等的数    
                j--;
            } else {
                res += 1;
                while(i<=j && Math.abs(nums[i])==num1)//去重
                    i++;
                while(i<=j && Math.abs(nums[j])==num2)//去重
                    j--;
            }
        }
        return res;
    }

对本题有疑问的同学，欢迎在评论区留言探讨~

**总结：**

面试中最常考的算法题主要是：数组、二叉树。期中呢，HashMap、HashSet等辅助数据结构使用比较多，“双指针法”在有序数组相关算法题中使用较多；无序数组，使用HashMap和HashSet较多；二叉树大多使用递归、dfs来解题。

另外，在实际面试中，算法也是这样一步步优化：最先提出的方案没有那么“优”也没有关系，如果面试官不满意，继续在此基础上进行优化，大多时候面试官会提示优化的方向。当然能直接给出优化方案最好~

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号**`菜鸟名企梦`**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**

![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）

[1240]: /images/20220505/f285453415054f4e9589d74efc2a5b81.png