求职 面试题:从长度为 1 万的有序且有重复数字的列表找出第一个 0 前面的一位数字和最后一个 0 后面的一个数字,例如 [...,-1,0,0,0,6,...] 打印-1 和 6,谢谢。

luckyhey · January 17, 2019 · Last by simple replied at January 21, 2019 · 2012 hits

面试题:从长度为1万的有序且有重复数字的列表找出第一个0前面的一位数字和最后一个0后面的一个数字,例如[...,-1,0,0,0,6,...]打印-1和6,谢谢。

共收到 45 条回复 时间 点赞

既然是有序的,那么0最多是集中出现1到连续多个0,所以python菜鸟觉得这样写(应该有高手可以简化写法):

arr=[-3,-2,-1,0,0,0,0,0,0,0,0,0,6,6,7]

for i in range(len(arr)):
if(i>0 and arr[i]==0):
if(arr[i-1] != 0): print(arr[i-1])
if(i<(len(arr)-1) and arr[i+1] !=0 ): print(arr[i+1])

最直观,笨拙的写法

def test(l):
t = []
m = []
for i in l:
if i == 0:
print(t[len(t)-1])
break
else:
t.append(i)

# print(l[::-1])
for n in l[::-1]:
if n == 0:
print(m[len(m)-1])
break
else:
m.append(n)

test([1,2,3,45,0,4,213,32,1,0,2])
KK 回复

有序的。。。

2log2(n)的时间复杂度。
每次取中间的数值去比较。。。

simple 回复

哈哈,审题不清,想着5分钟内写完。。瞄了一样就开始写了,随手写的。。不过我测试了下,我的这个有序无序都可以达到目标。

先把列表转换成字符串,再正则0+匹配重复0的长度,再分割。。。略复杂了😂

index()和lastIndex(),不知道python有没有类似的方法

菜鸡写法😅 不知道对不对
list=[-2,-1,0,6,0,0,7,0,8,14,22]
def check():
for i in range(len(list)):
if list[i]==0:
print(list[i-1])
break
for i in range(len(list) - 1, -1, -1):
if list[len(list)-1]==0:
print("最后一个数值为0")
break
if list[i]==0 and i<len(list)-1:
print(list[i + 1])
break

data = [-3,-2,-1,0,1,2,3,4,5,1,2,3,0,5,3,4,12,0,0,19]
data1 = [123,2,-1,-5,0,1,3,4,5,6,7,1,23,5,1,0,0,0,23,1,0,22]

def zeor_list(data):
print u'第一个0前面的一位数字的位置是:'+ str(data.index(0) + 1)
print u'第一个0前面的一位数字是:'+ str(data[data.index(0) - 1])
revered = data[::-1]
print u'最后一个0后面的一个数字的位置是: ' + str(len(revered) - revered.index(0) - 1)
print u'最后一个0后面的一个数字是: ' + str(revered[revered.index(0) - 1])

好像理解成无序有重复数字的了。。。

写的很垃圾。希望看到大牛的简单实现的思路

def get_result(number_list):
first,last = 0,0
lenth = len(number_list)
for i in range(1,lenth):
# print(lenth, i , lenth-i)
if number_list[i]==0 or number_list[lenth-i]==0:
if first ==0 and number_list[i]==0:
first = number_list[i-1]
print('found first :' ,first)
if last ==0 and number_list[lenth-i]==0:
last = number_list[lenth-i+1]
print('found first :', last)
if first == 0:
print('no 0 in the list')


# number_list = [-3,-2,-1,0,0,0,0,7,0,0,0,0,6,8,7]
number_list = [-3,-2,-1,0,6,8,7]
# number_list = [-3,-2,-1,6,8,7]
# number_list = [-2,-1,0,6,0,0,7,0,8,14,22]
get_result(number_list)
arr = [-3,-2,-1,0,0,0,3,6,8,9]
start = 0
end =len(arr)-1
found = False
if (arr[0]>=0 or arr[end]<=0):
print ('error')
while (start<end and not found):
mid = int((start+end)/2)
if (mid>0 and arr[mid] == 0 and arr[mid-1] <0):
found = True
print ('start:',arr[mid-1])
else:
if (arr[mid]<0):
start = mid+1
else:
end = mid
start = 0
end =len(arr)-1
found = False
while (start<end and not found):
mid = int((start+end)/2)
if (mid<len(arr)-1 and arr[mid] == 0 and arr[mid+1] >0):
found = True
print ('end:',arr[mid+1])
else:
if (arr[mid]<=0):
start = mid+1
else:
end = mid

result:
start: -1
end: 3

最近看了下Stream,感觉楼主抛出的这个问题用StreamAPI解决很简单呀,思路如下:
1.先将数组转换成流
2.将流中的0全部过滤掉
3.因为是有序的,剩下不是正数就是负数,那就正负各分一组
4.取正数组第一个和负数组最后一个即可

Map<Boolean, List<Integer>> collect = Arrays.asList(-2, -1, 0, 0, 0, 1, 2, 3).stream().filter(i -> {return i != 0;}).collect(groupingBy(i -> i > 0));
int aftNumber = collect.get(true).get(0);
int preNumber = collect.get(false).get(collect.get(false).size() - 1);

恩,看完楼上的回复发现大家都是自己实现的,好惭愧,我也来一个,思路如下:
1.定义两个标点,一个从数组的头开始,一个从数组的尾巴开始
2.一旦扫描到0,就停止循环,并打印出之前标点的位置

int[] arr = {-2, -1, 0, 0, 1, 2, 3};
int i = 0;
int j = arr.length - 1;
while(arr[i] != 0 && arr[i] < 0)
i++;
while(arr[j] !=0 && arr[j] > 0)
j--;
int preNumber = arr[i - 1];
int afrNumber = arr[j + 1];

set去重,判断0的位置

a = [0, 0, 0, 1, 2, 3]
def get_num(a):
a_set = set(a)
if len(a) == 1:
return "", ""
if 0 not in a_set:
return "", ""
a_set_sort = sorted(a_set)
num_0_index = a_set_sort.index(0)
if num_0_index == 0:
return "", a_set_sort[num_0_index+1]
elif num_0_index + 1 == len(a_set_sort):
return a_set_sort[num_0_index-1], ""
else:
return a_set_sort[num_0_index - 1], a_set_sort[num_0_index + 1]
cheunghr 回复

😀 ,python也是有的,不过面试官主要是想考察时间复杂度这些东西。

const arr = []
const fillArr = async (array) =>{
while (array.length < 10000) {
await array.push(5 - Math.round(Math.random() * 10))
}
return array
}

fillArr(arr).then((result) => {
const firstZero = result.indexOf(0)
const lastZero = result.lastIndexOf(0)
const before = result[firstZero - 1] ? result[firstZero - 1] : 'not exist. the first 0 is array's first element'
const last = result[lastZero + 1] ? result[lastZero + 1] : 'not exist. the first 0 is array's first element'
console.log(`before first 0: ${before}`)
console.log(`after last 0: ${last}`)
})

所用語言js....我承認我是來鬧場的,也寫完才看到大家都自己實現....(遠目

@autotester1
用正則搞不好好寫,用0+分割開來,然後取第一個的最後一個數跟最後一個的第一個數,只是中途看到取到負號的時候,才想到冏了

const arr = []
const fillArr = async (array) =>{
while (array.length < 10000) {
await array.push(5 - Math.round(Math.random() * 10))
}
return array
}

fillArr(arr).then((result) => {
const strRs = result.join(',').split(/0+/g)
const firstStr = strRs[0].replace(/^,|,$/g, '').split(/,+/g).pop()
const lastStr = strRs[strRs.length - 1].replace(/^,|,$/g, '').split(/,+/g).shift()
console.log(`before first 0: ${firstStr ? firstStr : 'not exist'}`)
console.log(`after last 0: ${lastStr ? lastStr : 'not exist'}`)
})

恩...有序序列(倒地

luckyhey 回复

这个真不难,撑死了LEETCODE EASY中间中等难度的。
大头条么?

magicyang 回复

大佬,帮忙看下,这样写是不是和你的时间复杂度是一样的:

int[] arr = {-2, -1, 0, 0, 0, 0, 1, 2, 3};
boolean flag = true;
int index = arr.length / 2;
while(flag){
if(arr[index] > 0){
index = index - (index/2);
} else if(arr[index] < 0){
index = index + (index/2);
} else{
int preIndex = index - 1;
int aftIndex = index + 1;
while(arr[preIndex] == 0)
preIndex--;
while(arr[aftIndex] == 0)
aftIndex++;
flag = false;
}
}

小白自己想的。

arr=[-3,-2,-1,0,0,0,0,0,0,0,0,0,6,6,7]
for i in range(len(arr)):
if arr[i]== 0:
if arr[i-1] != 0:
print(arr[i-1])
elif arr[i+1] != 0:
print(arr[i+1])
break
昨天有雨 回复

如果中间全是0就不是,还是O(n)级别的。
这是个二分查找的变种。

22Floor has been deleted
23Floor has been deleted

做两次二分查找


def binarySearch(testList):
if testList[0] >0 or testList[-1] < 0 or len(testList)< 3:
print "error"
midFlag1 = len(testList)/2
midFlag2 = len(testList)/2
reArray = []
while(1):
if testList[midFlag1] == 0 and testList[midFlag1 - 1] < 0:
print "item before first 0 is : %s" % testList[midFlag1 - 1]
reArray.append(testList[midFlag1 - 1])
break
if testList[midFlag1] >= 0 and midFlag1 > 0:
print(testList[midFlag1],midFlag1)
midFlag1 = midFlag1 / 2
if testList[midFlag1] < 0 and midFlag1 <len(testList) :
print(testList[midFlag1],midFlag1)
midFlag1 = (len(testList) -midFlag1)/2 + midFlag1
while(1):
if testList[midFlag2] == 0 and testList[midFlag2 + 1] > 0:
print "item After last 0 is : %s" % testList[midFlag2 + 1]
reArray.append(testList[midFlag2 + 1])
break
if testList[midFlag2] > 0 and midFlag2 > 0:
print(testList[midFlag2],midFlag2)
midFlag2 = midFlag2 / 2
if testList[midFlag2] <= 0 and midFlag2 <len(testList) :
print(testList[midFlag2],midFlag2)
midFlag2 = (len(testList) -midFlag2)/2 + midFlag2
return reArray
def main():
testList = [-4,-2,-1,0,0,0,0,0,3,4,5]
# testList = [-1,0,1]
Result = binarySearch(testList)

if __name__ == '__main__':
main()
magicyang 回复

那它算最优解了吗? 它的时间复杂度度应该也是2log2n

昨天有雨 回复

当然不算,2分查找是最差O(lgn)

def searchNum(array):
length = len(array)
left_first = 0
right_first = 0
left_last = length - 1
right_last = length - 1
left = None
right = None
while(1):
# left
left_mid = (left_last + left_first)//2
if array[left_mid]<0 and array[left_mid+1] == 0:
left = array[left_mid]
if array[left_mid] >= 0:
left_last = left_mid
if array[left_mid] < 0:
left_first = left_mid

# right
right_mid = (right_last + right_first)//2
if array[right_mid] > 0 and array[right_mid-1] == 0:
right = array[right_mid]
if array[right_mid] <=0:
right_first = right_mid
if array[right_mid] > 0:
right_last = right_mid

if left and right:
return left, right
28Floor has been deleted

本小白写法

30Floor has been deleted

看了好多贴代码的,如果开始和末尾是0,没有几个结果是对的,很多都会报错。测试思维呢,测试自己写的逻辑都不完整

cookie 回复

难得有人看到😀

33Floor has been deleted
cookie 回复

题目给出的条件已经定义了头和尾都不是0吧

arr = [-3,-2,-1,0,0,0,0,0,0,0,0,0,6,6,7]
print arr[arr.index(0)-1]
print arr[::-1][arr[::-1].index(0)-1]

如果可以调用python的index(),函数,这个东西非常简单。。。。

python标准库有二分查找的方法

import bisect
b =[-3,-2,-1,0,0,0,6,6,7]
left = bisect.bisect_left(b, 0)
right = bisect.bisect_right(b, 0, lo=left)
print(b[left-1],b[right] )

def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""


if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
cookie 回复

个人感觉在面试场景下如果没有特殊说明, 能实现就好了,从测试角度来说能写出来就好了,大部分公司算法只是加分项不是必需项, 那些要求很高的会要求你实现并写出单元测试,那就可以写的更健壮一点, 当然如果纯站在讨论解题上,还是需要考虑很多情况的

我的一家之言:
其实对测试和前端、移动端开发来说,你不去面试二线以上的公司是不会考你算法的。
主要是平时真的用不上。
顺带说一下,前面几楼,测试用例不按有序写,这个有点坑。
PS:也别说考算法完全没用,至少可以过滤掉一些基础特别差的人,有时候基础差的人沟通成本真的很高。

直接正则去匹配呢 ^-[1-9]{1}[0]+[1-9]{1}$ ,然后再处理匹配结果

我用了比较笨的方法,如果能有一键去重的方法,就好了。

public static void main(String[] args) {
int[] list = new int[]{-4,-3,-2,0,0,0,4,5,6};

int len = list.length;
int i=0,j=0,n=0;
int start = 0, end = len;
for(i=start;i< end;) {
n = (end - start) / 2;
if (list[n] > 0) {
end = n - 1;
}else if(list[n] < 0){
start = n + 1;
}else{
for(j=n;j>=0;j--){
if(list[j] != 0){
System.out.println("this is the value before 1st 0:" + list[j]);
break;
}
}
if(j<0){ System.out.println("the first value is 0.");}
for(j=n;j<len;j++){
if(list[j] != 0){
System.out.println("this is the value after last 0:" + list[j]);
break;
}
}
if(j==len){ System.out.println("the last value is 0.");}
break;
}
}

}

给定1万长度,从中点开始不断向两头二分判断中值是否为0,为0就继续往两边二分,不为0就往中间二分。预期复杂度应该是O(log2n)吧

def getNum(li):
if type(li) == list:
s = li.count(0)
if s == 0:
print 'list里没有0!'
else:
for i in range(len(li)):
if li[i] == 0:
if i == 0:
return 'error'
else:
return str(li[i - 1])
else:
return '输入参数需要是list类型的! 输入错误%s' % type(li)

调用时,调用两次getNum就好了,记得用反转一下list

def testGetNum():
li = []
# 随机生产list列表
for i in range(10):
li.append(random.choice([-1, -2, 0, 0, 0, 3, 0, 8, 6, 9, 4, 0, 5]))
print li
# 调用
a = getNum(li)
li.reverse() # 反转li
b = getNum(li)
print a
print b

结果
[4, -2, 0, 8, 0, 0, 9, -1, 0, -1]
-2
-1

把list中所有的0索引找出来,第一个索引-1,最后一个索引+1

list1 = [1,3,54,57,1,0,567,23,0,567,0,345,23,0,123,4,234,454,0,2,242,234]
num = -1
list2 = []
for i in list1:
if i == 0:
num = list1.index(i,num+1)
list2.append(num)
print list1[list2[0]-1]
print list1[list2[-1]+1]
1
2

话说有序的,序列保证第一个和最后一个数都不是0的话, 需要这么复杂吗,一个遍历就解决的事

L=[-3,-2,-1,0,0,0,3,6,8,9]
count1,count2=0,0
for index in range(len(L)):
if L[index]==0:
if count1==0:
print(L[index-1])
count1+=1
elif count1>0 and count2==0:
count2+=1
print(L[index])

这种题目我特别喜欢把list转换成str来处理

def fun(num_list):
num_str = ''.join(num_list)
first_index = num_str.index('0')-1
second_index = num_str[::-1].index('0')-1
print(num_str[first_index], num_str[::-1][second_index])
Lee 回复

嗯,正则(,0)+确实不好写😅

def get_num(list1):
list2=list(set(list1))
list2.sort()
index=list2.index(0)

numlen=len(list2)

if index>0 and index<numlen:
return list2[index-1],list2[index+1]
else:
return False

如何看待#面试题目都没看明白就开始答题的人?

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up