数组解题

发表于 | 分类于
字数统计: 2k | 阅读时长 ≈ 8

数组相关题_python版

寻找某个值的区间（leetcode 34 Search for a Range）

题目：这题要求在一个排好序可能有重复元素的数组里面找到包含某个值的区间范围。要求使用O(log n)的时间，所以我们采用两次二分查找。

For Example：
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        left = 0
        right = len(A) - 1      
        result = [-1, -1]
        while left <= right:
            mid = (left + right) / 2           
            if A[mid] > target:
                right = mid - 1
            elif A[mid] < target:
                left = mid + 1
            else: # 找到时
                result[0] = mid
                result[1] = mid
                
                i = mid - 1 # 向前找
                while i >= 0 and A[i] == target:
                    result[0] = i
                    i -= 1
                
                i = mid + 1 # 向后找
                while i < len(A) and A[i] == target:
                    result[1] = i
                    i += 1
                break
        return result

第K个数的问题

题目：这题是一道很好的面试题目，首先题目短小，很快就能说清题意而且有很多种解法。从简单到复杂的解法都有，梯度均匀。解决它不需要预先知道特殊领域知识。

这题有很多思路：

  1. 按从大到小全排序，然后取第k个元素，时间复杂度O(nlogn)，空间复杂度O(1)
  2. 利用堆进行部分排序。维护一个大根堆，将数组元素全部压入堆，然后弹出k次，第k个就是答案。时间复杂度O(klogn)O(klogn)，空间复杂度O(n)O(n)
  3. 选择排序，第k次选择后即可得到第k大的数，时间复杂度O(nk)，空间复杂度O(1)

以上三种方法时间复杂度太高。下面介绍两种更好的方法：

维持K大小的堆排序（优先队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
用容量为K的最大堆来存储最小的K个数。最大堆的堆顶元素就是最小K个数中的最大的一个。每次扫描一个数据X，如果X比堆顶元素Y大，则不需要改变原来的堆。如果X比堆顶元素小，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最大堆的结构，需要调整堆来维持堆的性质。用优先队列思想也一样，只不过k大小的队列每次移动的元素量较大，堆会好一些。
'''
# 使用了heapq的内置数据结构，用了一个trick 因为默认是创建小顶堆，所以在添加元素的时候加个 负号就变成大顶堆了。


import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if k > len(tinput) or k == 0: return []
        heap = []
        for num in tinput:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heapreplace(heap, -num)
        return sorted(list(map(lambda x: x*-1, heap)))

快速排序，时间复杂度近似O（n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
'''
def qselect(A,k):
    if len(A)<k:return A
    pivot = A[-1]
    right = [pivot] + [x for x in A[:-1] if x>=pivot]
    rlen = len(right)
    if rlen==k:
        return right
    if rlen>k:
        return qselect(right, k)
    else:
        left = [x for x in A[:-1] if x<pivot]
        return qselect(left, k-rlen) + right
 
for i in range(1, 10):
    print qselect([11,8,4,1,5,2,7,9], i)

求根算法（ LeetCode 69）

题目：计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

思路一：直接从1到x/2之间遍历，判断是否是平方根的条件是，i*i小于等于x并且小于等于x并且(i+1)*(i+1)大于x，则返回i。超时 。

思路二：二分查找法。初始化i=0，j=x，mid=0。进入循环，找到中间值mid = (i + j) / 2，如果mid>x / mid，表示mid不是平方根，且数值过大，则j=mid。如果mid小于等于x / mid，则判断(mid + 1) > x / (mid + 1)，表示mid*mid小于x，并且mid再加1后的平方就会比x大，这表示mid就是那个平方根，返回mid。否则表示mid过小，i=mid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0 or x==1:
            return x
        i=0
        j=x
        mid=0
        while True:
            mid=(i+j)/2
            if mid>x/mid:
                j=mid
            else:
                if (mid+1)>x/(mid+1):
                    return mid
                i=mid

数组中后面的数减前面的数的差的最大值

题目：如何求数组中数对差最大。数对差是指一个数组中某两个元素a和b（并且a排在b的前面），a减去b所得到的差值。

思路一：遍历存储最大值

思路二：首先求出数组中任意一对相邻的数据之间的差值，得到一个新的数组。如果某两个数据之间的数对差最大，也就是说这两个数据之间的差值最大。假设这两个数据的位置是i和j，那么这两个位置之间的数据是a[i]，a[i+1]，a[i+2]……，a[j-1]，a[j]。那么a[i]-a[j]=(a[i]-a[i+1])+(a[i+1]-a[i+2])+……(a[j-1]-a[j])，括号中的数据是相邻数据的差值，都已经在前面求出来了。然后这个问题就转化为了求数组中连续的子数组和最大的问题，这个问题可以通过动态规划问题求出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import random
def Max(firstNum,secondNum):
	if firstNum>=secondNum:
		return firstNum
	else:
		return secondNum
 
def Count(array):
	gapArray=[]
	length=len(array)
	#遍历一遍记录相邻两个之间的gap
	for i in xrange(length-1):
		gap=array[i]-array[i+1]
		gapArray.append(gap)
	#转化为子集合最大和问题
	max=-((1<<32)-1)
	sum=0
	for i in xrange(len(gapArray)):
		sum+=gapArray[i]
		max=Max(max,sum)
		if sum<0:
			sum=0
	return max
 
array=[]
for i in xrange(20):
	array.append(random.randint(0,50))
print array
print "max gap:"+str(Count(array))

合并多个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#采用归并排序算法
#拆解到最后，实际变成两个数组进行排序
def MergeSort(nums):
    #请牢记传入的参数是多维数组
    #此处是递归出口
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    
    #记住此处得到的也是多维数组
    Left = MergeSort(nums[:mid])
    Right = MergeSort(nums[mid:])

    #print(Left[0], Right[0])
    #要传入的参数是数组中第一个索引处的值
    return Sort_list(Left[0], Right[0])

def Sort_list(Left, Right):
    #存储排序后的值
    res = []
    a = 0
    b = 0

    while a < len(Left) and b < len(Right):
 
        if Left[a] < Right[b]:
            res.append(Left[a])
            a += 1
        else:
            res.append(Right[b])
            b += 1
    res = res + Left[a:] + Right[b:]
    # 转为二维数组
    res = [res]
    return res

两个有序数组求差集

思路一：依次取出较小数组的元素，然后再另外一个数组上进行二分查找

思路二：用齐头并进的两个下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def intersect(self, nums1, nums2):
        nums3 = []
        nums1.sort()
        nums2.sort()
        m = len(nums1)
        n = len(nums2)
        i = 0
        j = 0
        while i<m and j<n:
            if nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                i += 1
        return nums3

两个集合如何求并集，交集；

1
2
3
4
5
6
7
python集合支持一系列标准操作，包括并集、交集、差集和对称差集，例如：  

a = t | s          # t 和 s的并集  
  
b = t & s          # t 和 s的交集  
  
c = t – s          # 求差集（项在t中，但不在s中）

给定一个数组求中位数

(中位数，就是数组排序后处于数组最中间的那个元素)

思路：和TOP k问题一样，这里就不写了。（先排序再取中位数不优）

-------------Thanks for Reading!-------------