程序员老鬼

某老板:试用期结束了,你没通过考核,试用期没有工资!

这老板算盘打得也太响了吧,隔着屏幕都能听见。

试用期结束了,老板一句“你没通过考核”,然后顺手补一句“试用期没有工资”。好家伙,合着员工这几个月不是上班,是来公司做公益的?每天打卡、干活、被安排任务,最后考核不通过就想一分钱不给,这不是管理,这是耍赖。

Image

试用期考核没过,可以不转正,这个大家都懂。可你不能把人家的劳动当没发生啊。人已经坐那儿干了活,公司也用了成果,工资就该给。别一提试用期就跟老板开了免单券一样,想怎么说就怎么说。

这种话最气人的地方不是“没通过”,而是那种理直气壮。好像员工没留下来,公司就白亏了。问题是,打工人也耗了时间、精力、通勤,还可能错过别的机会。

今日面试题

标题:移除元素这题,别真的去“删除”

数组 [3,2,2,3],要移除 3。

很多人第一眼就想:把 3 删掉,后面的元素往前挪。

这地方我一般会先拦一下,数组不是链表,别一上来就想着删。Java 里的数组长度是固定的,题目真正要的也不是把数组变短,而是把不等于 val 的元素搬到数组前面,然后返回有效长度。

比如:

nums = [3, 2, 2, 3]
val = 3

处理完以后,只要前面变成这样就行:

[2, 2, _, _]

后面两个位置是什么,题目不关心。判题的时候也只看前 k 个元素。

这题最稳的写法,是用一个写入位置 write。

read 负责从头往后扫,write 负责记录下一个正常元素应该放到哪里。

代码可以这么写:

classSolution{
publicintremoveElement(int[] nums, int val){
int write = 0;

for (int read = 0; read < nums.length; read++) {
int current = nums[read];

if (current == val) {
continue;
            }

            nums[write] = current;
            write++;
        }

return write;
    }
}

这段代码不花哨,但现场我更愿意写这种。

因为它的状态很少,出错点也少。你不用管后面的元素怎么处理,不用每删一个就整体搬一次,也不用反复改数组边界。

拿刚才那个例子走一遍:

nums = [3, 2, 2, 3]
val = 3
write = 0

read = 0,看到 3,等于 val,跳过。

read = 1,看到 2,不是 val,写到 nums[0]。

数组变成:

[2, 2, 2, 3]
write = 1

别被这个数组吓到,后面那个 2 是旧值,现在还没必要管。

read = 2,又看到 2,写到 nums[1]。

[2, 2, 2, 3]
write = 2

read = 3,看到 3,跳过。

最后返回 2。判题只看前两个元素,就是 [2,2]。

这题有个很容易写歪的版本:

for (int i = 0; i < nums.length; i++) {
if (nums[i] == val) {
// 后面所有元素往前搬
    }
}

这种写法不是不能做,但你要处理下标回退,还要处理连续多个 val 的情况。比如:

[0, 1, 2, 2, 3, 0, 4, 2]
val = 2

连续两个 2 挨在一起时,如果你搬完以后 i 继续往后走,就可能漏检查一个位置。算法题里这种 bug 很烦,看起来只差一行,调半天。

所以我更习惯把它拆成两个动作:

一个指针只读,不回头。

一个指针只写,写完才往前走。

这个思路其实在线上代码里也常见。比如过滤一批脏数据、压缩一个临时数组、把有效记录前置,都可以这么干。不要一边遍历一边删,一边删一边改下标,后面八成要补锅。

复杂度也简单。

整个数组只扫一遍,时间复杂度是 O(n)。

没有额外开新数组,只用了两个变量,空间复杂度是 O(1)。

这题真正考的不是“会不会删除元素”,而是你有没有看懂题目那句:原地修改,返回新长度。

数组没变短,变短的是你承认的那一段长度。