算法笔记-数组

发表于 | 分类于 ，

数组的考点（关键字）主要包括三个，分别是查找、排序、位运算以及数的特点。和字典（哈希表）、字符串有交叉，主要和考察数组中数的个数这类型的题目相关。

一.查找

要掌握二分查找，因为它的时间复杂度比按顺序查找快（数组不为有序的情况下）。二分查找法一共三个指针，分别是left,right,mid。判断mid指向的数是否是要查找的数，不是的话，left = mid+1 或者 right = mid-1。下面是使用的例子。注意mid的赋值要在循环里面写，循环的跳出条件为left>right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def GetFirstK(data,k,start,end):
    if start > end:
        return -1
    middleIndex = (start+end)//2
    middleData = data[middleIndex]
    if middleData ==k:
        if (middleIndex >0 and data[middleIndex-1] != k) or middleIndex == 0:
            return middleIndex
        else:
            end = middleIndex -1
    elif middleData >k:
        end = middleIndex-1
    else:
        start = middleIndex+1
    return GetFirstK(data,k,start,end)

查找问题还往往和数的特点结合，例如奇偶性、数的数量等。这类问题可以用位运算来帮助解决。有几种常用的位运算技巧或者性质必须掌握：
1.辨别奇偶性：

这是利用了奇数和偶数的二进制表示的最后一位不同的性质。

1
2
def is_even(num):
    return num&1 == 0

2.相同的数通过异或后得到的结果为零。利用这个性质，我们可以在其他的数字都出现两次，只有一个数出现一次的数组中获得这个数。

1
2
3
4
5
6
7
a,b = 0,0
#这里是找两个只出现一次的数的代码片段
for i in array:
    if IsR(pos,i):
        a ^= i
    else:
        b ^= i

3.位移某一个二进制表示的数。下面是右移。

1
tmp >>= 1

二.排序

必须掌握常用的排序方法，比如说快排。下面是快排的代码：

1
2


还有一种排序很重要，那就是自定义排序。python的两个版本的写法有点不一样，这个也是必须掌握的。

1
2


三.相关数据结构

1.字典（哈希表）

主要是在考察数组中数的个数的问题中使用。举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers,duplication):
        dic = {}
        for num in numbers:
        		#添加关键字操作
            if not num in dic:
                dic[num] = 1
            #对字典的键值对操作
            else:
                dic[num] += 1
        for num in numbers:
            if dic[num] != 1:
                duplication[0] = num
                return True
        return False

2.字符串

也是用在考察数组中数的个数的题目中。转换的技巧如下（两者互转）：

1
2
3
4
#数组转字符串
s = ''.join(numbers)
#字符串转数组
nunbers = list(s)

之后用字符串中的count函数以及filter关键字来筛选出符合要求的数：

1
tmp = list(filter(lambda c: s.count(c) >1,s))
请作者喝杯咖啡吧！