数组基础
数据简介
数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据。
内存地址： 1000 1004 1008 1012 1016 1020 1024
数据元素： 10 23 24 31 45 78 88
下标索引： 0 1 2 3 4 5 6
- 线性表：线性表就是所有数据元素排成像一条线一样的结构，线性表上的数据元素都是相同类型，且每个数据元素最多只有前、后两个方向。数组就是一种线性表结构，此外，栈、队列、链表都是线性表结构。
- 连续的内存空间：线性表有两种存储结构：「顺序存储结构」和「链式存储结构」。其中，「顺序存储结构」是指占用的内存空间是连续的，相邻数据元素之间，物理内存上的存储位置也相邻。数组也是采用了顺序存储结构，并且存储的数据都是相同类型的。
计算机给一个数组分配了一组连续的存储空间，其中第一个元素开始的地址被称为 「首地址」。每个数据元素都有对应的下标索引和内存地址，计算机通过地址来访问数据元素。当计算机需要访问数组的某个元素时，会通过 「寻址公式」 计算出对应元素的内存地址，然后访问地址对应的数据元素。
// C++ 的数组实现
int arr[2][3] = {
{1, 2, 3,},
{4, 5, 6}
}
// java 的数组实现
int [][]arr = new int[2][3]{
{1, 2, 3},
{4, 5, 6}
}
# python 的数组实现
arr = [
[1, 2, 3],
[4, 5, 6]
]
数组基本操作
# 数组
arr = [1, 4, 7, 1, 3]
# 访问元素
def value(nums, i) -> (int):
if 0 <= i <= len(nums) - 1:
return nums[i]
print(value(arr, 4))
# 查找元素
def find(nums, val) -> (int):
for i in range(len(nums))
if nums[i] == value:
return i
else
return -1
print(find(arr, 2))
# 插入元素
value = 9
arr.append(value)
arr.insert(2, value)
print(arr)
# 改变元素
def change(nums, i, val) -> (bool):
if 0 <= i <= len(nums) - 1:
nums[i] = val
return true
else
return false
print(change(arr, 1, 6))
# 删除元素
arr.pop()
arr.remove(0)
数组排序
冒泡排序
冒泡排序（Bubble Sort）基本思想：
经过多次迭代，通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面。
def bubbleSort(nums:[int]) -> None: # 时间复杂度：O(n^2)
n = len(nums)
if (n < 2):
return
for i in range(n-1, 0, -1):
for j in range(0, i, 1):
if nums[j] > nums[j+1]:
nums[j+1], nums[j] = nums[j], nums[j+1]
选择排序
选择排序（Selection Sort）基本思想：
将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择一个值最小的元素，放到已排序区间的末尾，从而将该元素划分到已排序区间。
def selectionSort(nums:[int]) -> None: # 时间复杂度：O(n^2)
n = len(nums)
if (n < 2):
return
for i in range(0, n-1, 1):
min = i
for j in range(i+1, n, 1):
min = j if nums[j] < nums[min] else min
nums[min], nums[i] = nums[i], nums[min]
插入排序
插入排序（Insertion Sort）基本思想：
将数组分为两个区间：左侧为有序区间，右侧为无序区间。每趟从无序区间取出一个元素，然后将其插入到有序区间的适当位置。
def insertionSort(nums:[int]) -> None: # 时间复杂度：O(n^2)
n = len(nums)
if n < 2:
return
for i in range(1, n, 1):
base, j = nums[i], i - 1
while j >= 0 and nums[j] > base:
nums[j+1] = nums[j]
j -= 1
nums[j+1] = base
希尔排序
希尔排序（Shell Sort）基本思想：
将整个数组切按照一定的间隔取值划分为若干个子数组，每个子数组分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子数组和对子数组进行插入排序。直至最后一轮排序间隔为 111，对整个数组进行插入排序。
def shellSort(nums:[int]) -> None: # 时间复杂度：O(nxlogn) ~ O(n^2)
size = len(nums)
if size < 2:
return
gap = size // 2
while gap > 0:
for i in range(gap, size, 1):
base, j = nums[i], i - gap
while j >= 0 and nums[j] > base:
nums[j+gap] = nums[j]
j -= gap
nums[j+gap] = base
gap = gap // 2
归并排序
归并排序（Merge Sort）基本思想：
采用经典的分治策略，先递归地将当前数组平均分成两半，然后将有序数组两两合并，最终合并成一个有序数组。
def merge(nums:[int], left:int, mid:int, right:int) -> None:
temp = [0 for _ in range(right-left+1)]
i, j, k = left, mid + 1, 0
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp[k] = nums[i]
k += 1
i += 1
elif nums[i] >= nums[j]:
temp[k] = nums[j]
k += 1
j += 1
while i <= mid:
temp[k] = nums[i]
k += 1
i += 1
while j <= right:
temp[k] = nums[j]
k += 1
j += 1
for k in range(0, right-left+1, 1):
nums[left+k] = temp[k]
def mergeSort(nums:[int], left:int, right:int) -> None: # 时间复杂度：O(nxlogn)
if left >= right:
return
mid = left + ((right - left) >> 1)
mergeSort(nums, left, mid)
mergeSort(nums, mid+1, right)
merge(nums, left, mid, right)
快速排序
快速排序（Quick Sort）基本思想：
采用经典的分治策略，选择数组中某个元素作为基准数，通过一趟排序将数组分为独立的两个子数组，一个子数组中所有元素值都比基准数小，另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序，以达到整个数组有序。
# 快排 v1.0 时间复杂度：O(nxlogn)
def partition(nums:[int], left: int, right: int) -> int:
i, j = left,right
while i < j:
while i < j and nums[j] <= num[left]:
j--
while i < j and nums[i] >= nums[left]:
i++
nums[i], nums[j] = nums[j], nums[i]
nums[left], nums[i] = nums[i], nums[left]
return i
def quickSort(nums:[int], left: int, right: int) -> None:
n = len(nums)
if n < 2:
return
pivot = partition(nums, left, right)
quickSort(nums, left, pivot)
quickSort(nums, pivot+1, right)
# 快排 v2.0 时间复杂度：O(nxlogn)
def partition(nums: [int], left: int, right: int) -> [int]:
less, more = left - 1, right
while left < more:
if nums[left] < nums[right]:
less += 1
nums[left], nums[less] = nums[less], nums[left]
left += 1
elif nums[left] > nums[right]:
more -= 1
nums[left], nums[more] = nums[more], nums[left]
else:
left += 1
nums[more], nums[right] = nums[right], nums[more]
return [less+1, more]
def quickSort(nums: [int], left: int, right: int) -> None:
if left >= right:
return
random.seed(time.time())
base = random.randint(left, right)
nums[left+base], nums[right] = nums[right], nums[left+base]
arr = partition(nums, left, right)
quickSort(nums, left, arr[0]-1)
quickSort(nums, arr[1]+1, right)
堆排序
堆（Heap）：一种满足以下两个条件之一的完全二叉树：
- 大顶堆（Max Heap）：任意节点值 ≥ 其子节点值。
- 小顶堆（Min Heap）：任意节点值 ≤ 其子节点值。
堆排序（Heap sort）基本思想：
借用「堆结构」所设计的排序算法。将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆结构继续维持大顶堆性质。
def heapInsert(nums: [int], index: int) -> None:
while index > 0 and nums[index] > nums[(index - 1) // 2]:
nums[index], nums[(index - 1) // 2] = nums[(index - 1) // 2], nums[index]
index = (index - 1) // 2
def heapify(nums: [int], index: int, heapSize: int) -> None:
left = index * 2 + 1
while left < heapSize:
largest = left + 1 if left + 1 < heapSize and nums[left+1] > nums[left] else left
largest = largest if nums[largest] > nums[index] else index
if largest == index:
break
nums[largest], nums[index] = nums[index], nums[largest]
index = largest
left = index*2 + 1
def heapSort(nums: [int]) -> None: # 时间复杂度： O(nxlogn)
heapSize = len(nums)
if heapSize < 2:
return
for i in range(heapSize):
heapInsert(nums, i)
heapSize -= 1
nums[0], nums[heapSize] = nums[heapSize], nums[0]
while heapSize > 0:
heapify(nums, 0, heapSize)
heapSize -= 1
nums[0], nums[heapSize] = nums[heapSize], nums[0]
计数排序
计数排序（Counting Sort）基本思想：
通过统计数组中每个元素在数组中出现的次数，根据这些统计信息将数组元素有序的放置到正确位置，从而达到排序的目的。
def countingSort(nums:[int]) -> [int]: # 时间复杂度: O(n+k)
nums_min, nums_max = min(nums), max(nums)
size = nums_max - nums_min + 1
counts = [0 for _ in range(size)]
for num in nums:
counts[num - nums_min] += 1
for i in range(1, size):
counts[i] += counts[i-1]
res = [0 for _ in range(len(nums))]
for i in range(len(nums)-1, -1, -1):
num = nums[i]
res[counts[num - nums_min] - 1] = num
counts[num - nums_min] -= 1
return res
桶排序
桶排序（Bucket Sort）基本思想：
将待排序数组中的元素分散到若干个「桶」中，然后对每个桶中的元素再进行单独排序。
def insertionSort(nums:[int]) -> None:
n = len(nums)
if n < 2:
return
for i in range(1, n, 1):
base, j = nums[i], i - 1
while j >= 0 and nums[j] > base:
nums[j+1] = nums[j]
j -= 1
nums[j+1] = base
def bucketSort(nums: [int], bucket_size=5) -> [int]: # 时间复杂度: O(nxlogn/m)
nums_min, nums_max = min(nums), max(nums)
bucket_count = (nums_max - nums_min) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for num in nums:
buckets[(num - nums_min) // bucket_size].append(num)
res = []
for bucket in buckets:
insertionSort(bucket)
res.extend(bucket)
return res
基数排序
基数排序（Radix Sort）基本思想：
将整数按位数切割成不同的数字，然后从低位开始，依次到高位，逐位进行排序，从而达到排序的目的。
def maxBits(nums: [int]) -> int:
maxN = 1 << 31
n = len(nums)
for i in range(n):
maxN = max(maxN, nums[i])
res = 0
while maxN != 0:
res += 1
maxN /= 10
return res
def getDigit(x: int, d: int) -> int:
return int((x / int(pow(10, d - 1))) % 10)
def process(nums: [int], left: int, right: int, digit: int) -> None:
radix = 10
i, j = 0, 0
bucket = [0 for _ in range(right-left+1)]
for d in range(1, digit+1, 1):
count = [0 for _ in range(radix)]
for i in range(left, right+1, 1):
j = getDigit(nums[i], d)
count[j] += 1
for i in range(1, radix, 1):
count[i] = count[i] + count[i-1]
for i in range(right, left-1, -1):
j = getDigit(nums[i], d)
bucket[count[j] - 1] = nums[i]
count[j] -= 1
j = 0
for i in range(left, right+1, 1):
nums[i] = bucket[j]
j += 1
def radixSort(nums: [int]) -> None: # 时间复杂度：O(nxk)
n = len(nums)
if n < 2:
return
process(nums, 0, n-1, maxBits(nums))
二分查找
二分查找（一）
二分查找算法（Binary Search Algorithm）：也叫做折半查找算法、对数查找算法，是一种用于在有序数组中查找特定元素的高效搜索算法。
二分查找算法是经典的 「减而治之」 的思想。
这里的 「减」 是减少问题规模的意思，「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即：每一次查找，排除掉一定不存在目标元素的区间，在剩下可能存在目标元素的区间中继续查找。
def binary_search(nums: [int], target: int) -> int:
left, right = 0, len(nums) - 1;
while left <= right:
mid = left + ((right - left) >> 1)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return -1
二分查找（二）
二分查找的一些关键在于：
- 1.区间的开闭问题；
- 2.中值的取值问题；
- 3.出界条件的判断；
- 4.搜索区间范围的选择。
数组双指针
双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。
对撞指针
对撞指针：指的是两个指针 left、right 分别指向序列的第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两指针值相撞，或者满足其他要求的特殊条件为止。
快慢指针
快慢指针：指两个指针从同一侧开始遍历序列，且移动步长一个快一个慢。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件为止。
分离双指针
分离双指针：两个指针分别属于不同的数组，两个指针分别在两个数组中移动。
数组滑动窗口
滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。
- 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。
- 缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。
固定长度滑动窗口
固定长度滑动窗口算法（Fixed Length Sliding Window）：在给定数组 / 字符串上维护一个固定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。
不定长滑动窗口
不定长度滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。