哈希(3) - 判断一个数组是否为另一个数组的子集
例如:
输入: 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中的元素3,不存在于arr1中。
方法1(简单方法):
使用两个循环来处理:外层的循环遍历arr2的每个元素。内层的循环逐个的取元素与外层传入的元素进行比较。如果所有元素都匹配成功,则返回1,否则返回0。
#include<iostream> //如果arr2是arr1的子集,则返回1. bool isSubset(int arr1[], int arr2[], int numArr1, int numArr2) { int i = 0; int j = 0; for (i = 0; i < numArr2; i++) { for (j = 0; j < numArr1; j++) { if (arr2[i] == arr1[j]) break; } //如果上面的内层循环没有break, 则说明arr2不是arr1的子集 if (j == numArr1) return 0; } //如果执行到这里,说明arr2是arr1的子集 return 1; } int main() { int arr1[] = { 11, 1, 13, 21, 3, 7 }; int arr2[] = { 11, 3, 7, 1 }; int numArr1 = sizeof(arr1) / sizeof(arr1[0]); int numArr2 = sizeof(arr2) / sizeof(arr2[0]); if (isSubset(arr1, arr2, numArr1, numArr2)) std::cout<<"arr2[] is subset of arr1[]"; else std::cout<<"arr2[] is not a subset of arr1[]"; return 0; }时间复杂度: O(m*n)
方法2 (使用排序和二分搜索)
1) 对arr1[]进行排序, 平均O(mLogm)
2) 对arr2[]中的每个元素, 在已排序的arr1[]中进行二分查找.
a) 如果没有找到这个元素,则返回0.
3) 如果所有元素都找到,则返回1.
#include <iostream> //函数声明 。两个辅助函数,用于判断子集。 void quickSort(int *arr, int si, int ei); int binarySearch(int arr[], int low, int high, int x); // 如果arr2[]是arr1[]的一个子集,则返回1 bool isSubset(int arr1[], int arr2[], int numArr1, int numArr2) { int i = 0; quickSort(arr1, 0, numArr1-1); for (i=0; i<numArr2; i++) { if (binarySearch(arr1, 0, numArr1-1, arr2[i]) == -1) return 0; } //如果执行到了这里,说明arr2是arr1的子集 return 1; } //---------辅助函数begin-------- //标准的二分查找函数 int binarySearch(int arr[], int low, int high, int x) { if(high >= low) { int mid = (low + high)/2; //或者low + (high - low)/2; /* * 检测arr[mid]是否为第一次遇到x。 * 当x满足下面情况的一种时,则证明是第一次遇到x: (1) (mid == 0) && (arr[mid] == x) (2) (arr[mid-1] < x) && (arr[mid] == x) */ if(( mid == 0 || arr[mid-1] < x) && (arr[mid] == x)) return mid; else if(x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid -1), x); } return -1; } template<typename type> void exchange(type *a, type *b) { type temp; temp = *a; *a = *b; *b = temp; } int partition(int A[], int si, int ei) { int x = A[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if(A[j] <= x) { i++; exchange(&A[i], &A[j]); } } exchange (&A[i + 1], &A[ei]); return (i + 1); } /* 实现快速排序的函数 A[]:需要排序的数组 si:Starting index ei:Ending index */ void quickSort(int A[], int si, int ei) { int pi; //Partitioning index if(si < ei) { pi = partition(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } //---------辅助函数end-------- int main() { int arr1[] = {11, 1, 13, 21, 3, 7}; int arr2[] = {11, 3, 7, 1}; int numArr1 = sizeof(arr1)/sizeof(arr1[0]); int numArr2 = sizeof(arr2)/sizeof(arr2[0]); if(isSubset(arr1, arr2, numArr1, numArr2)) std::cout<<"arr2[] is subset of arr1[]"; else std::cout<<"arr2[] is not a subset of arr1[]"; return 0; }时间复杂度: O(mLogm + nLogm). 其中,mLogm是排序算法的平均复杂度。因为上面用的是快速排序,如果是最坏情况,则复杂度会变为O(m^2)。
方法3 (使用排序和归并 )
1) 对两个数组arr1和arr2分别排序。O(mLogm + nLogn)
2) 使用归并流程来检测已排好序的数组arr2是否存在于排好序的arr1中。
//如果arr2是arr1的子集,则返回1 bool isSubset(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; if(m < n) return 0; quickSort(arr1, 0, m-1); quickSort(arr2, 0, n-1); while( i < n && j < m ) { if( arr1[j] <arr2[i] ) j++; else if( arr1[j] == arr2[i] ) { j++; i++; } else if( arr1[j] > arr2[i] ) return 0; } if( i < n ) return 0; else return 1; }时间复杂度: O(mLogm + nLogn) 。比方法2要好。
方法4 (使用哈希)
1) 给数组arr1的所有元素创建一个哈希表.
2) 遍历数组arr2,并检测其中的每个元素是否存在于哈希表中。如果哈希表中没有找到元素,则返回0.
3) 如果所有元素都找到了,则返回1.
注意:方法1,2,4都没有处理arr2数组中有重复元素的情况。例如,{1, 4, 4, 2} 实际上不是 {1, 4, 2}的子集, 但上述的这些方法会认为是子集。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。