Tập con C++ của mảng

Phương pháp 2. Mã trong C

// Write a program to check whether Array is a subset of another array in C
#include

int binarySearch(int arr[], int low, int high, int x);

int isSubset(int arr1[], int arr2[], int m, int n)
{
    int i = 0;
 
    for (i = 0; i < n; i++) {
     if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1) 
        return 0; 
     } 
     return 1;
}

int binarySearch(int arr[], int low,int high, int x) { if (high >= low)
    {
        /*low + (high - low)/2;*/
        int mid = (low + high) / 2;
 
        if ((mid == 0 || x > arr[mid - 1]) && (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;
}
 
// Driver code
int main()
{
    int arr1[] = { 11, 10, 13, 21, 30, 70 };
    int arr2[] = { 11, 30, 70, 10 };
 
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    
    for(int i=0; iarr1[j]){
                int temp = arr1[i];
                arr1[i] = arr1[j];
                arr1[j] = temp;
            }
        }
    }
    if (isSubset(arr1, arr2, m, n))
        printf("arr2[] is subset of arr1[] ");
    else
        printf("arr2[] is not a subset of arr1[]");
 
    return 0;
}

• Viết chương trình kiểm tra xem một mảng có phải là tập con của một mảng khác hay không

Cho 2 mảng số nguyên Array1 và Array2 có kích thước lần lượt là M và N(N <= M). Chúng ta phải kiểm tra xem Array2 có phải là tập hợp con của Array1 hay không

Mảng A là tập con của mảng B khác nếu mỗi phần tử của A đều có mặt trong B

Ví dụ.

Input Array1 : 3, 5, 7, 12, 1, 9, 10, 0, 2
Input Array2 : 1, 3, 5, 9

Array2 is subset of Array1
-----------------------------
Input Array1 : 3, 5, 7, 12, 1, 9, 10, 0, 2
Input Array2 : 6, 3, 8

Array2 is not a subset of Array1

---

Cho Array1 và Array2 lần lượt là 2 mảng số nguyên kích thước M và N và ta muốn kiểm tra xem Array2 có phải là tập con của Array1 hay không.

Bạo lực. O(M*N)

• Tìm kiếm từng phần tử của Array2 trong Array1 bằng tìm kiếm tuyến tính. Nếu tất cả các phần tử của Array2 đều có trong Array1 thì Array2 là tập con của Array1, ngược lại thì không.

Thời gian phức tạp. O(O(M*N))

Chương trình C để kiểm tra xem một mảng có phải là tập hợp con của một mảng khác không

#include
 
/* Checks if array2 is subset of array1 */
int isSubsetArray(int *array1, int size1, int *array2, int size2) {
    int i, j;
    
    /* search every element of array2 in array1. If 
 all elements of array 2 is found in array1 then 
 array2 is subset of array1 otherwise not */
    for (i = 0; i < size2; i++) {
        for (j = 0; j < size1; j++) {
           if(array2[i] == array1[j])
              /* Element found */
              break;
        }
         
        if(j == size1)
        /* array2[i] not found in array1 */
           return 0;
    }
     
    /* All elements of array2 found in array1 */
    return 1;
}
  
int main() {
    int array1[9] = {3, 5, 7, 12, 1, 9, 10, 0, 2};
    int array2[4] = {1, 3, 5, 9};
 
    if(isSubsetArray(array1, 9, array2, 4))
      printf("array2 is subset of array1");
    else
      printf("array2 is not a subset of array1");     
 
    return 0;
}

Đầu ra

array2 is subset of array1

---

Bằng cách sắp xếp Array1
Chúng ta có thể cải thiện độ phức tạp về thời gian của thuật toán trên bằng cách sắp xếp Array1 trước. Bây giờ, chúng ta có thể tìm kiếm từng phần tử của Array2 trong Array1 bằng tìm kiếm nhị phân.

• Sắp xếp mảng1. O(MLogM)
• Tìm kiếm từng phần tử của Array2 trong Array1 đã sắp xếp bằng tìm kiếm nhị phân. NLogM
• Nếu tất cả các phần tử của Array2 đều có trong Array1 thì Array2 là tập con của Array1, ngược lại thì không

Thời gian phức tạp. O(MLogM + NLogM)

#include

/* Swap array element at index left and right */
void swap(int array[], int left, int right) {
    int temp;
    /* Swapping using a temp variable */
    temp = array[left];
    array[left]=array[right];
    array[right]=temp; 
}
 
void quickSort(int array[], int left, int right) {
    int pivot; 
    if (right > left) {
      /* Partition the given array into 
      two segment by calling partion function */
        pivot = partition(array, left, right);
     
        /* Recursively sort left and right sub array*/
        quickSort(array, left, pivot-1);
        quickSort(array, pivot+1, right);
    }
}
 
int partition(int array[], int left, int right) {
    int temp = left;
    int pivot = array[left];
    
    while(left < right) {
        /* From left side, search for a number
      greater than pivot element */ 
        while(array[left] <= pivot) 
            left++;
        /* From right side, search for a number 
      less than pivot element */ 
        while(array[right] > pivot) 
            right--;
    
        /*Swap array[left] and array[right] */
        if(left < right) 
            swap(array, left, right);
    }
   /* Put pivot element in it's currect position '*/ 
   array[temp] = array[right];
   array[right] = pivot;
   /* Return partition index. All elements left of 
   right index is < pivot whereas elements right 
   side of right index are > pivot element */ 
   return right;
}

/* Standard implementation of binary search */
int bSearch(int *array, int left, int right, int K) {
  if(right >= left) {
    int mid = (left + right)/2; 
    /* k is equal to array[mid] */ 
    if(array[mid] == K)
        return mid;
    else if(K > array[mid])
    /* Search of right sub tree */
      return bSearch(array, (mid + 1), right, K);
    else
    /* search on left sub tree */
      return bSearch(array, left, (mid -1), K);
  }
  /* K not foundin array */
  return -1;
}

/* Checks if array2 is subset of array1 */
int isSubsetArray(int *array1, int size1, int *array2, int size2) {
    int i, j;
    /* Sort array1 */
    quickSort(array1, 0, size1-1);
    
    /* search every element of array2 in array1. If 
 all elements of array 2 is found in array1 then 
 array2 is subset of array1 otherwise not */
    for (i = 0; i < size2; i++) {
        if(bSearch(array1, 0, size1, array2[i]) == -1)
            return 0;
    }
     
    /* All elements of array2 found in array1 */
    return 1;
}
  
int main() {
    int array1[9] = {3, 5, 7, 12, 1, 9, 10, 0, 2};
    int array2[4] = {1, 3, 5, 9};
 
    if(isSubsetArray(array1, 9, array2, 4))
      printf("array2 is subset of array1");
    else
      printf("array2 is not a subset of array1");     
 
    return 0;
}

Đầu ra

array2 is subset of array1

---

Bằng cách sử dụng Hashing

• Tạo bảng băm và khởi tạo nó bằng 0.
• Thêm từng phần tử của Array1 vào hashtable
• Traverse Array2 và cho từng phần tử Array2[i] kiểm tra xem nó có tồn tại trong hashtable hay không
• Nếu tất cả các phần tử của Array2 đều có trong hashtable thì Array2 là tập con của Array1, ngược lại thì không

Thời gian phức tạp. Trên)

Làm thế nào để có được một tập hợp con của một mảng trong C?

Tập hợp con của một mảng là gì?

Có cắt mảng trong C không?

Làm cách nào để lấy độ dài mảng trong C?