Tìm số còn thiếu trong mảng C++

Tìm một phần tử bị thiếu trong một mảng được sắp xếp

Nếu các phần tử được lưu trữ trong một mảng, thì chúng ta phải tìm

1. Phần tử duy nhất còn thiếu trong mảng đã sắp xếp
2. Nhiều phần tử bị thiếu trong mảng được sắp xếp
3. Thiếu phần tử trong mảng chưa sắp xếp

Có thể có nhiều hơn một cách khả thi để tìm phần tử còn thiếu. Vì vậy, hãy xem xét phương pháp thứ nhất

Phương pháp 1

Ở đây chúng tôi đã lấy một ví dụ về một mảng có kích thước 11. Đây là những số tự nhiên 'n' đầu tiên. Vì vậy, chuỗi bắt đầu từ 1 trở đi. Nếu bạn để ý mảng trên, 7 là phần tử còn thiếu. Bây giờ chúng ta phải tìm ra 7 còn thiếu trong chuỗi trên

Ta biết công thức của n số tự nhiên đầu tiên là. n (n+1) / 2. Vì vậy, nếu tôi có tổng cộng 12 phần tử là phần tử cuối cùng, chúng ta nên biết về phần tử cuối cùng. Tổng của n số tự nhiên đầu tiên có thể được biết bằng cách sử dụng – n (n+1) / 2. Chúng ta có thể sử dụng công thức này nếu chúng ta biết phần tử đầu tiên và phần tử cuối cùng. Vì vậy, tổng là

Vì vậy, tổng tất cả các phần tử có trong mảng phải là 78. Nếu không phải là 78 ​​thì ít đi bao nhiêu, đó sẽ là yếu tố còn thiếu của chúng ta. Như vậy là chúng ta đã tính tổng bằng công thức, bây giờ chúng ta cộng từng phần tử của mảng và trừ đi số đó đi 78. Hãy xem nào

Dưới đây là đoạn mã giả để tìm tổng của từng phần tử trong mảng bằng phương pháp lặp

Mã giả

sum = 0;
for (int i = 0; i < 11; i++){
 sum = sum + C [i]
}

Bây giờ chúng ta có tổng của mảng trong biến tổng của chúng ta. Vậy bây giờ làm thế nào để tính phần tử còn thiếu?

Phần tử bị thiếu = 78 – tổng

= 78 – 71

= 7

Vì vậy, đây là phương pháp đầu tiên để tìm phần tử đơn lẻ trong một mảng được sắp xếp

Mã đầy đủ bằng ngôn ngữ C

#include 
#include 

struct List{
 int C[15];
 int size;
 int length;
};

void Display(struct List list) {
 int i;
 printf("Elements are:\n");
 for (i = 0;i đầu ra
Phương pháp thứ 2
Ở đây phần tử còn thiếu không nằm trong n số tự nhiên đầu tiên. Trình tự có thể bắt đầu từ bất kỳ điểm nào
Ở đây, số mảng bắt đầu là 6 và số cuối cùng là 17 và đây là tổng cộng 11 số (0 đến 10). Đây không phải là tổng của n số tự nhiên đầu tiên. Đầu tiên, chúng ta phải biết các phần tử đầu tiên và cuối cùng là 6 và 17. Trong mảng này, 12 là phần tử còn thiếu
Vậy ta có số nhỏ nhất, số cao nhất và số phần tử lần lượt là L=6, H=17, N=11. Ở đây chúng ta sẽ tìm thấy các yếu tố còn thiếu với sự trợ giúp của các chỉ số. Sự khác biệt giữa
Phần tử thứ 1 và chỉ số thứ 0 là. 6 – 0 = 6
Phần tử thứ 2 và chỉ mục thứ 1 là. 7 – 1 = 6
phần tử thứ 3 và chỉ số thứ 2 là. 8 – 2 = 6
phần tử thứ 4 và chỉ số thứ 3 là. 9 – 3 = 6
phần tử thứ 5 và chỉ số thứ 4 là. 10 – 4 = 6
phần tử thứ 6 và chỉ số thứ 5 là. 11 – 5 = 6
phần tử thứ 7 và chỉ số thứ 6 là. 13 – 6 = 7
Ở đây, sự khác biệt phổ biến là 6 và ở chỉ số thứ 6, chúng tôi có sự khác biệt là 7. Vì vậy, đây là yếu tố còn thiếu. Vì vậy, yếu tố còn thiếu là gì? . Vì vậy, chúng ta phải thêm một sự khác biệt chung với số chỉ mục mà phần tử bị thiếu
Sự khác biệt + số chỉ mục = phần tử bị thiếu
6 + 6 = 12
Bây giờ chúng ta có phần tử còn thiếu là 12. Vì vậy, logic rất đơn giản, chúng ta phải dừng lại ở chỉ số mà chúng ta đã tìm thấy sự thay đổi về sự khác biệt của phần tử và chỉ số
Mã giả
difference = low – 0;
for (i = 0; i < n; i++){
 if (C [i] – i != difference){
  printf (“Missing element %d\n”, i + difference);
  break;
             }
}
Thời gian phức tạp. Trên)
Mã đầy đủ bằng ngôn ngữ C
#include 
#include 

struct List{
 int C[15];
 int size;
 int length;
};

void Display(struct List list) {
 int i;
 printf("Elements are:\n");
 for (i = 0;i đầu ra
Ở đây chúng tôi đã biết phần tử bị thiếu chỉ là 12 nên chúng tôi dừng lại ở chỉ mục nơi chúng tôi tìm thấy phần tử bị thiếu. Nhưng nếu muốn tìm nhiều phần tử ta sẽ tìm tiếp đến cuối mảng. Chúng ta sẽ thấy điều đó trong bài viết tiếp theo
Trong bài viết tiếp theo, tôi sẽ thảo luận về Tìm nhiều phần tử bị thiếu trong một mảng được sắp xếp bằng ngôn ngữ C với các ví dụ. Ở đây, trong bài viết này, tôi cố gắng giải thích Cách tìm một phần tử bị thiếu trong một mảng được sắp xếp trong C với các ví dụ và tôi hy vọng bạn sẽ thích bài viết này Tìm phần tử bị thiếu trong một mảng được sắp xếp trong C với các ví dụ