二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- 逐行逐列包里查找
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not array:
return
for i in range(row):
for j in range(col):
if array[i][j]==target:
return True
return False
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not array:
return
for row in array:
if target in row:
return True
return False
- 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。所以左上是最小，右下是最大。从左下角开始搜索或者右上角开始会比较简单处理。如果使用左下角开始，逐个对比，比目标小就右移，比目标大就上移。直到找到目标。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not array:
return
row=len(array)
col=len(array[0])
i = row - 1
j = 0
while (i >= 0 and j <= col-1) :
if array[i][j] == target:
return True
elif array[i][j] < target:
j += 1
elif array[i][j] > target:
i -= 1
return False
【tips】：
- while loop 边界条件
数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
- 逐个读取储存至列表，如果出现重复直接输出
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
record = []
for i in numbers:
if i in record:
duplication[0] = i
return True
else:
record.append(i)
return False
【tips】：
.append增列表复杂度低于+- 需要不断用
in查询，整体复杂度较高 O(n2)
- Counter
# -*- coding:utf-8 -*-
import collections
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
flag=False
c=collections.Counter(numbers)
for k,v in c.items():
if v>1:
duplication[0]=k
flag=True
break
return flag
【tips】：
-
import collections
c=collections.Counter(numbers)详解
Counter，dict的子类，计算可hash的对象
>>> from collections import *
>>> c = Counter()
>>> c
Counter()
>>> c = Counter("gallahad")
>>> c
Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
>>> b = Counter({'red':4,'blue':2})
>>> b
Counter({'red': 4, 'blue': 2})
>>> a = Counter(cats = 4,dogs = 8)
>>> a
Counter({'dogs': 8, 'cats': 4})
Counter 对象常见操作
>>> c
Counter({'a': 5, 'b': 4, 'd': 2, 'c': -3})
>>> sum(c.values())# 统计所有的数目
>>> list(c)# 列出所有唯一的元素
['a', 'c', 'b', 'd']
>>> set(c)# 转换为set
set(['a', 'c', 'b', 'd'])
>>> dict(c)# 转换为常规的dict
{'a': 5, 'c': -3, 'b': 4, 'd': 2}
>>> c.items()# 转换为(elem,cnt)对构成的列表
[('a', 5), ('c', -3), ('b', 4), ('d', 2)]
>>> c.most_common()[:-4:-1]# 输出n个数目最小元素
[('c', -3), ('d', 2), ('b', 4)]
>>> c += Counter()# 删除数目为0和为负的元素
>>> c
Counter({'a': 5, 'b': 4, 'd': 2})
>>> Counter(dict(c.items()))# 从(elem,cnt)对构成的列表转换为counter
Counter({'a': 5, 'b': 4, 'd': 2})
>>> c.clear()# 清空counter
>>> c
Counter()
>>> c = Counter(a=3,b=1,c=-2)
>>> d = Counter(a=1,b=2,c=4)
>>> c+d#求和
Counter({'a': 4, 'b': 3, 'c': 2})
>>> c-d#求差
Counter({'a': 2})
>>> c & d#求交集
Counter({'a': 1, 'b': 1})
>>> c | d#求并集
Counter({'c': 4, 'a': 3, 'b': 2})
-
items
列表的形式返回可以遍历的值
voc2 = {'name':'xin','sex':'male','job':'AI'}
output = voc2.items()
print(type(output))
# <class 'dict_items'>
print(output)
# dict_items([('name', 'xin'), ('sex', 'male'), ('job', 'AI')])
for k,v in output:
print(k,v)
# name xin
# sex male
# job AI
【Q】：
-
Counter返回值中是按照出现次序降序排列，但是在遍历items时却是按原有出现顺序遍历。
Why？
- 长度为n的数组里的所有数字都在0到n-1的范围内，所以可以利用现有数组设置标志，不需要额外数组或者 hash table.
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
length = len(numbers)
for i in range(length):
val = numbers[i]
if val >= length:
val -= length
if numbers[val] >= length:
duplication[0] = val
return True
numbers[val] = numbers[val] + length
return False
- 类似3的思路，但是更方便。
遍历一次，依次把对应位上数字变负，重复见到的时候对应位会负负得正的，直接输出
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
for i in range(len(numbers)):
val = abs(numbers[i])
numbers[val] = -numbers[val]
if numbers[val] > 0:
duplication[0] = val
return True
return False
构建乘积数组
给定一个数组A[0,1,...,n-1],
请构建一个数组B[0,1,...,n-1],
其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。
不能使用除法。
注意：规定
B[0] = A[1] * A[2] * ... * A[n-1]，
B[n-1] = A[0] * A[1] * ... * A[n-2];
- 按照题目，两次遍历完成
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
Alength = len(A)
B = [None]*Alength
for x in range(Alength):
val = 1
for y in range(Alength):
if y != x:
val *= A[y]
B[x] = val
return B
-
B[i] 的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
先算下三角中的连乘:B[i] = B[i-1] * A[i-1]
然后倒过来按上三角中的分布规律，把另一部分也乘进去。
| B0 | 1 | A1 | A2 | ... | A n-2 | A n-1 |
|---|---|---|---|---|---|---|
| B1 | A0 | 1 | A2 | ... | A n-2 | A n-1 |
| B2 | A0 | A1 | 1 | ... | A n-2 | A n-1 |
| ... | ... | ... | ... | ... | ... | ... |
| Bn-3 | A0 | A1 | ... | 1 | A n-2 | A n-1 |
| B n-2 | A0 | A1 | ... | A n-3 | 1 | A n-1 |
| B n-1 | A0 | A1 | ... | A n-3 | A n-2 | 1 |
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
if not A:
return []
Alength = len(A)
B = [None] * Alength
# 左下角乘一遍 后一项比前一项多一个也就是说
#B[i] = B[i-1] * A[i-1]
B[0] = 1
for i in range(1,Alength):
B[i] = B[i-1] * A[i-1]
# 右上角同理，不过需要反着来
print(B)
tmp = 1
for i in range(Alength-2, -1, -1):
B[i] = B[i+1] * A[i+1]
return B
【Q】：
后半段计算如果写成：
for i in range(Alength-2, -1, -1):
B[i] = B[i+1] * A[i+1]
return B
结果不对，为什么？怎么改
Reference
[1] 牛客网在线编程 - 剑指Offer
[2] Python3 collections模块使用详解
[3] python之Counter,items,sorted,count
网友评论