求职 面试题：从长度为 1 万的有序且有重复数字的列表找出第一个 0 前面的一位数字和最后一个 0 后面的一个数字，例如 [...,-1,0,0,0,6,...] 打印-1 和 6，谢谢。
面试题：从长度为 1 万的有序且有重复数字的列表找出第一个 0 前面的一位数字和最后一个 0 后面的一个数字，例如 [...,-1,0,0,0,6,...] 打印-1 和 6，谢谢。
既然是有序的，那么 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])
2log2(n) 的时间复杂度。
每次取中间的数值去比较。。。
先把列表转换成字符串，再正则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]
，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'}`)
})
恩...有序序列 (倒地
对
magicyang
回复
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
做两次二分查找
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()
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
本小白写法
看了好多贴代码的，如果开始和末尾是 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 标准库有二分查找的方法
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
回复
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])
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
如何看待# 面试题目都没看明白就开始答题的人？