散列是指使用称为散列函数的数学公式从可变大小的输入生成固定大小的输出的过程。该技术确定数据结构中项目存储的索引或位置。
互联网上的数据每天都在成倍增加,有效存储这些数据始终是一个难题。在日常编程中,这些数据量可能不是那么大,但仍然需要轻松高效地存储、访问和处理。用于此目的的一种非常常见的数据结构是数组数据结构。
现在问题来了,如果数组已经存在,还需要一个新的数据结构吗!答案就在“效率”二字。虽然存储在数组中需要 O(1) 时间,但搜索至少需要 O(log n) 时间。这个时间看起来很小,但是对于大型数据集来说,它可能会导致很多问题,进而使数组数据结构效率低下。 所以现在我们正在寻找一种可以在恒定时间内(即 O(1) 时间)存储数据并在其中进行搜索的数据结构。这就是哈希数据结构发挥作用的方式。随着哈希数据结构的引入,现在可以轻松地在恒定时间内存储数据并在恒定时间内检索数据。
哈希主要包含三个组成部分:
散列的组成部分
假设我们有一组字符串 {“ab”, “cd”, “efg”} 并且我们希望将其存储在表中。
我们这里的主要目标是在 O(1) 时间内快速搜索或更新表中存储的值,并且我们不关心表中字符串的顺序。因此给定的一组字符串可以充当键,而字符串本身将充当字符串的值,但是如何存储与键对应的值呢?
将键映射到数组的索引
上述技术使我们能够使用简单的哈希函数计算给定字符串的位置,并快速找到存储在该位置的值。因此,散列的想法似乎是在表中存储数据(键,值)对的好方法。
哈希函数创建键和值之间的映射,这是通过使用称为哈希函数的数学公式来完成的。散列函数的结果称为散列值或散列。哈希值是原始字符串的表示,但通常小于原始字符串。
例如:将数组视为 Map,其中键是索引,值是该索引处的值。因此,对于数组 A,如果我们有索引i,它将被视为键,那么我们只需查看 A[i] 处的值即可找到该值。 只需查找 A[i]。
给定两个数组:arr1[0..m-1] 和 arr2[0..n-1]。判断 arr2[] 是否是arr1[] 的子集。两个数组都没有按顺序排列。可以假设两个数组中的元素是不同的。
例子:
输入:arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1} 输出:arr2[] 是 arr1[] 的子集 输入:arr1[] = {1, 2, 3, 4, 5, 6}, arr2[] = {1, 2, 4} 输出:arr2[] 是 arr1[] 的子集 输入:arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3} 输出:arr2[] 不是 arr1[] 的子集
使用两个循环:外层循环一一选取 arr2[] 的所有元素。内循环线性搜索外循环选取的元素。如果找到所有元素则返回 1,否则返回 0。
下面是上述方法的实现:
#Python 3程序,用于查找一个数组是否是另一个数组的子集
#如果arr2 []是arr1 []的子集,则返回1
def isSubset(arr1, arr2, m, n):
i = 0
j = 0
for i in range(n):
for j in range(m):
if(arr2[i] == arr1[j]):
break
# 如果上面的内部循环根本没有被中断,那么arr2[i]在arr1[]中不存在。
if (j == m):
return 0
# 如果我们到达这里,那么所有 arr2[] 中的元素都存在 在 arr1[] 中
return 1
if __name__ == "__main__":
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if(isSubset(arr1, arr2, m, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[]")
arr2[] 是 arr1[] 的子集
时间复杂度: O(m*n) 辅助空间: O(1)
这个想法是对给定的数组 arr1[] 进行排序,然后对 arr2[] 中的每个元素在排序的 arr1[] 中进行二分搜索。如果未找到该元素则返回 0。如果所有元素都存在则返回 1。
步骤:
给定数组arr1[] = { 11, 1, 13, 21, 3, 7 }和arr2[] = { 11, 3, 7, 1 }。 步骤 1:我们对数组 arr1[] 进行排序,得到 arr1[] = { 1, 3, 7, 11, 13, 21}。 步骤 2:我们将使用二分查找在 arr1[] 中查找 arr2[] 中的每个元素。
当找到所有元素后,我们可以得出 arr2[] 是 arr1[] 的子集。
算法:
该算法非常简单。
下面是上述方法的代码实现:
def isSubset(arr1, arr2, m, n):
i = 0
quickSort(arr1, 0, m-1)
for i in range(n):
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1):
return 0
# 如果我们到达这里,那么所有元素
# arr2[] 中的所有元素都存在于 arr1[] 中
return 1
def binarySearch(arr, low, high, x):
if(high >= low):
mid = (low + high)//2
if((mid == 0 or x > arr[mid-1]) and (arr[mid] == x)):
return mid
elif(x > arr[mid]):
return binarySearch(arr, (mid + 1), high, x)
else:
return binarySearch(arr, low, (mid - 1), x)
return -1
def partition(A, si, ei):
x = A[ei]
i = (si - 1)
for j in range(si, ei):
if(A[j] <= x):
i += 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[ei] = A[ei], A[i + 1]
return (i + 1)
# 实现快速排序
# A[] --> 待排序数组
# si --> 起始索引
# ei --> 结束索引
def quickSort(A, si, ei):
# 分区索引
if(si < ei):
pi = partition(A, si, ei)
quickSort(A, si, pi - 1)
quickSort(A, pi + 1, ei)
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if(isSubset(arr1, arr2, m, n)):
print("arr2[] is subset of arr1[] ")
else:
print("arr2[] is not a subset of arr1[] ")