Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách in tần suất của từng ký tự trong một chuỗi bằng Python
Tần số của mỗi ký tự trong một chuỗi
Đối với điều đó, chúng tôi có hai phương pháp
- Sử dụng logic cơ bản
- phương thức truy cập []
Hãy bắt đầu với cái đầu tiên
câu lệnh if-else [Logic cơ bản]
Trước hết, hãy lấy một chuỗi mà chúng ta phải tìm tần số của mỗi ký tự
my_string = "Nitesh Jhawar"
Chúng tôi sẽ xác định một từ điển trống, freq_dict. Từ điển này sẽ chứa từng ký tự và tần số của nó trong các cặp khóa-giá trị. Ví dụ,
freq_dict={'N'. 1,'tôi'. 1}
Phím đại diện cho ký tự và tần số đại diện cho tần số tương ứng của nó
freq_dict = {}Bây giờ, đã đến lúc sử dụng vòng lặp for
for i in my_string:
if i in freq_dict:
freq_dict[i]=freq_dict[i] + 1
else:
freq_dict[i] = 1Ở đây, chúng tôi đã sử dụng một vòng lặp for để lặp qua các ký tự trong my_string bằng cách sử dụng biến lặp i
Sau đó, chúng ta sử dụng câu lệnh if-else. Nếu tôi tồn tại trong từ điển của chúng tôi, thì chúng tôi sẽ tăng số lượng tần suất lên 1, nếu không, chúng tôi sẽ khởi tạo giá trị thành 1
Cuối cùng, chúng tôi cần in từ điển của mình
print ["Characters with their frequencies:\n",freq_dict]
Và đầu ra sẽ là,
Characters with their frequencies:
{'N': 1, 'i': 1, 't': 1, 'e': 1, 's': 1, 'h': 2, ' ': 1, 'J': 1, 'a': 2, 'w': 1, 'r': 1}
phương thức truy cập []
Trong Python, chúng tôi có một mô-đun có tên là bộ sưu tập. Nó là một thùng chứa được sử dụng để lưu trữ dữ liệu như từ điển, danh sách, v.v. mô-đun bộ sưu tập chứa phương thức Counter[] cũng là vùng chứa lưu trữ dữ liệu ở dạng từ điển i. e, các phần tử là khóa và tần số của nó là giá trị
cú pháp
Bộ đếm [string_name]
Bây giờ, hãy sử dụng nó
from collections import Counter my_string = "Nitesh Jhawar" freq_dict = Counter[my_string] print ["Characters with their frequencies:\n",freq_dict]
Từ mô-đun bộ sưu tập, chúng tôi có một phương thức Counter đã nhập
Từ điển được trả về bởi Counter[] được lưu trữ trong freq_dict. Sau đó nó được in ra bằng câu lệnh print
chìa khóa rút ra. Một vấn đề tuyệt vời để học cách giải quyết vấn đề bằng cách sắp xếp và cấu trúc dữ liệu như BST và bảng băm. Chúng tôi đang lưu trữ thông tin bổ sung để sắp xếp chuỗi theo thứ tự ổn định
Hãy hiểu vấn đề
Cho xâu S, hãy viết chương trình sắp xếp xâu theo thứ tự giảm dần dựa trên tần suất xuất hiện của các ký tự
- Tần suất của một ký tự là số lần nó xuất hiện trong chuỗi
- Ở đầu ra, các ký tự có tần suất xuất hiện cao hơn sẽ xuất hiện trước
- Nếu hai ký tự có cùng tần số thì ký tự nào xuất hiện sớm nhất trong S phải đến trước. Nói cách khác, việc sắp xếp phải ổn định
- Giả sử chuỗi bao gồm các chữ cái tiếng Anh viết hoa và viết thường. Chúng ta cần coi chữ hoa và chữ thường của cùng một ký tự là khác nhau
Lưu ý quan trọng. Trước khi chuyển sang các giải pháp, chúng tôi khuyên bạn nên thử giải bài toán này trên giấy trong ít nhất 15 hoặc 30 phút. Thích giải quyết vấn đề
ví dụ 1
Đầu vào. S = "cây", Đầu ra. "eetr"
Giải trình. 'e' xuất hiện hai lần trong khi 'r' và 't' đều xuất hiện một lần. Vì vậy, 'e' phải xuất hiện trước cả 'r' và 't'
ví dụ 2
Đầu vào. S = "ccaaaAA", Đầu ra. "aaaccAA"
Giải trình. 'a' xuất hiện ba lần trong khi 'c' và 'A' xuất hiện hai lần. Vì vậy, 'a' phải xuất hiện trước cả 'c' và 'A'. Tương tự, tần số của 'c' và 'A' là như nhau. Để duy trì trật tự ổn định 'c' phải xuất hiện trước 'A'
Thảo luận phương pháp giải quyết
- Cách tiếp cận vũ phu bằng cách sử dụng các vòng lặp lồng nhau
- Cách tiếp cận giải pháp sử dụng cây tìm kiếm nhị phân
- Một giải pháp hiệu quả sử dụng bảng băm
Cách tiếp cận giải pháp 1. Cách tiếp cận vũ phu bằng cách sử dụng các vòng lặp lồng nhau
ý tưởng giải pháp
Để sắp xếp các ký tự dựa trên tần suất xuất hiện của chúng
- Chúng ta nên xác định từng ký tự duy nhất trong chuỗi đầu vào
- Chúng ta cũng cần biết tần số của từng ký tự duy nhất
- Việc sắp xếp phải ổn định, vì vậy chúng ta cần thiết kế một phương pháp để phân biệt vị trí của các ký tự có cùng tần số theo thứ tự đã sắp xếp. Trong một tình huống như vậy. Một ký tự xuất hiện đầu tiên trong chuỗi đầu vào phải xuất hiện trước trong đầu ra được sắp xếp
Vậy làm thế nào để đảm bảo những điều trên?
- Chúng tôi tạo một bộ nhớ bổ sung và lưu trữ số lần xuất hiện đầu tiên của mỗi ký tự chuỗi đầu vào duy nhất
- Bây giờ chúng tôi sắp xếp bộ nhớ bổ sung này dựa trên số lần xuất hiện và lần xuất hiện đầu tiên. Chúng tôi đang lưu trữ lần xuất hiện đầu tiên vì một lý do đơn giản. Điều này sẽ giúp chúng tôi duy trì sự sắp xếp ổn định. Nói cách khác, nếu hai ký tự có cùng tần số, ký tự có chỉ số đầu tiên thấp hơn sẽ xuất hiện trước trong đầu ra được sắp xếp
- Chúng tôi duyệt qua danh sách được sắp xếp ở trên và trích xuất tất cả các ký tự dựa trên số tần số của chúng trong một bộ nhớ bổ sung có kích thước n
các bước giải quyết
Chúng tôi định nghĩa một lớp hoặc cấu trúc UniqueChar, lưu trữ ba thông tin liên quan đến mỗi ký tự duy nhất. giá trị ký tự, số lần đếm và lần xuất hiện đầu tiên trong chuỗi đầu vào
struct UniqueChar { char ch int freqCount int firstIndex }- Bây giờ, chúng tôi khai báo một danh sách bổ sung freq[], trong đó mỗi phần tử lưu trữ loại đối tượng UniqueChar i. e. tần số véc tơ. Chúng tôi đang lấy một danh sách, không phải một mảng, vì chúng tôi không biết số lượng ký tự duy nhất trong chuỗi đầu vào. Một ý tưởng sẽ rõ ràng. Kích thước của danh sách này sẽ bằng tổng số ký tự duy nhất
Bây giờ chúng tôi chạy một vòng lặp lồng nhau để xác định từng ký tự duy nhất và lưu số lần xuất hiện đầu tiên và tần số của chúng trong danh sách freq[]. Ở đây, vòng lặp bên ngoài lặp qua từng ký tự và vòng lặp bên trong kiểm tra lần xuất hiện duy nhất của nó trong danh sách freq[]
- Đối với mỗi ký tự S[i], chúng tôi kiểm tra xem nó đã tồn tại trong danh sách freq[] hay chưa. Nếu có, chúng tôi tăng số lượng tần số của nó lên 1
- Nếu không, nó sẽ là lần xuất hiện đầu tiên của S[i]. Vì vậy, chúng tôi chèn S[i] vào danh sách freq[] với tần suất được tính là 1 và chỉ số i là lần xuất hiện đầu tiên
- Sau các vòng lặp lồng nhau, freq[] lưu trữ tất cả các ký tự duy nhất cùng với thông tin bổ sung
for [int i = 0; i < n; i = i + 1] { bool found = false for [int j = 0; j < freq.length; j = j + 1] { if [S[i] == freq[j].ch] { freq[j].freqCount = freq[j].freqCount + 1 found = true break } } if [found == false] { UniqueChar temp temp.ch = S[i] temp.freqCount = 1 temp.firstIndex = i freq.push_back[temp] } }Bây giờ chúng tôi sắp xếp danh sách freq[] dựa trên số lượng ký tự tần số. Nếu số lượng tần số bằng nhau cho hai phần tử, trước tiên chúng ta nên xử lý phần tử có First Index thấp hơn. Quy trình sắp xếp của chúng tôi có thể sử dụng bộ so sánh để đảm bảo điều này
________số 8_______
Sau đó, chúng tôi trích xuất các ký tự từ danh sách freq[] đã sắp xếp và lưu trữ nó trong một mảng đầu ra bổ sung result[n]
char result[n] int k = 0 for [int i = 0; i < freq.length; i = i + 1] { for [int j = 0; j < freq[i].freqCount; j = j + 1] { result[k] = freq[i].ch k = k + 1 } }- Cuối cùng, chúng tôi trả về mảng result[] làm đầu ra
Mã giải pháp C++
phân tích giải pháp
Giả sử có m ký tự duy nhất trong chuỗi đầu vào. Độ phức tạp thời gian = Độ phức tạp thời gian lưu trữ giá trị trong danh sách freq[] + Độ phức tạp thời gian sắp xếp danh sách freq[] + Độ phức tạp thời gian lưu trữ đầu ra trong result[] = O[mn] + O[m] + O[n] = O[
Tại sao độ phức tạp về thời gian của việc sắp xếp freq[] list O[m]? . Nếu chỉ có các chữ cái tiếng Anh viết hoa và viết thường là một phần của đầu vào, thì chỉ có thể có 52 ký tự duy nhất có thể được lặp lại nhiều lần. Vì vậy, chúng ta có thể sử dụng ý tưởng sắp xếp nhóm để sắp xếp đầu vào trong thời gian O[m]. Nói cách khác, không cần sử dụng các thuật toán sắp xếp dựa trên so sánh như sắp xếp hợp nhất hoặc sắp xếp theo đống. Nghĩ
Độ phức tạp của không gian = Không gian bổ sung của danh sách freq[] + Không gian bổ sung được sử dụng bằng cách sắp xếp + Lưu trữ kết quả[] mảng = O[m] + O[1] + O[n] = O[m + n]
Cách tiếp cận giải pháp 2. Sử dụng cây tìm kiếm nhị phân
ý tưởng giải pháp
Theo cách tiếp cận trên, các vòng lặp lồng nhau chiếm ưu thế về độ phức tạp thời gian, là O[nm]. Nếu chúng ta quan sát vòng lặp. Chúng tôi đang tìm kiếm sự hiện diện duy nhất của từng ký tự trong danh sách freq[] và chèn nó với thông tin bổ sung. Vì vậy, một ý tưởng là rõ ràng. Tìm kiếm là một hoạt động quan trọng cần O[m] thời gian cho mỗi ký tự trong trường hợp xấu nhất. Câu hỏi quan trọng là. Chúng ta có thể sử dụng một số cấu trúc dữ liệu hiệu quả khác để cải thiện độ phức tạp về thời gian của việc tìm kiếm không?
Cây tìm kiếm nhị phân có thể là một cấu trúc dữ liệu hữu ích cho các truy vấn tìm kiếm thường xuyên, trong đó độ phức tạp về thời gian phụ thuộc vào chiều cao của cây. Mặc dù, nếu chúng ta sử dụng ý tưởng về cây tìm kiếm nhị phân cân bằng chẳng hạn như Cây AVL hoặc cây Đỏ-Đen, thì độ phức tạp thời gian trong trường hợp xấu nhất để tìm kiếm, chèn và xóa sẽ là O[logn]
Chúng ta có thể sử dụng cấu trúc nút sau để lưu trữ từng ký tự duy nhất trong BST với hai tham số bổ sung. freqCount để lưu số lần đếm tần suất và firstIndex cho chuỗi lần xuất hiện đầu tiên
Ghi chú. Chúng tôi sẽ giả sử một BST cân bằng để triển khai
class BSTNode
{
char ch
int freqCount
int firstIndex
BSTNode *left
BSTNode *right
}các bước giải quyết
- Chúng tôi tạo một BST bằng cách chèn từng ký tự duy nhất từ chuỗi đầu vào. Trước khi chèn ký tự S[i] vào BST ta kiểm tra xem nó đã có chưa. Nếu đúng như vậy, chúng tôi tăng số lượng tần số lên 1. Mặt khác, chúng tôi chèn một nút mới với tần suất là 1 và i là lần xuất hiện đầu tiên
- Giờ đây, chúng tôi tạo một danh sách đối tượng bổ sung tần số[] [giống như giải pháp trên] và thực hiện duyệt BST theo thứ tự để lưu trữ các ký tự duy nhất cùng với các chi tiết khác trong tần số[]
- Bây giờ chúng ta làm theo quy trình của cách tiếp cận trước
- Chúng tôi sắp xếp danh sách freq[] dựa trên số lượng ký tự tần suất trong khi duy trì thứ tự ổn định
- Chúng tôi trích xuất các ký tự từ danh sách freq[] đã sắp xếp và lưu trữ nó trong một mảng đầu ra bổ sung result[n]
- Cuối cùng, chúng tôi trả về mảng result[] làm đầu ra
Mã giải pháp C++
phân tích giải pháp
Giả sử có m ký tự duy nhất trong chuỗi đầu vào
Độ phức tạp thời gian = Độ phức tạp thời gian chèn từng ký tự trong BST + Độ phức tạp thời gian trích xuất các ký tự vào danh sách freq[] bằng cách sử dụng truyền tải theo thứ tự + Độ phức tạp thời gian sắp xếp danh sách freq[] + Độ phức tạp thời gian lưu trữ đầu ra trong kết quả[] = O[nlogm] +
Độ phức tạp của không gian = Không gian bổ sung cho BST + Không gian bổ sung để lưu trữ freq[] + Không gian bổ sung để lưu trữ kết quả[] + Không gian bổ sung được sử dụng bằng cách sắp xếp = O[m] + O[m] + O[n] + O[1] =
Giải pháp hiệu quả bằng cách sử dụng bảng băm
ý tưởng giải pháp
Chúng ta có thể cải thiện độ phức tạp về thời gian hơn nữa bằng cách sử dụng bảng băm không? . Câu hỏi quan trọng là. Đưa ra một bảng băm các ký tự với tần số của chúng, làm thế nào chúng ta có thể thực hiện sắp xếp ổn định trên đó? . Chúng ta có thể sử dụng một bảng băm khác lưu trữ lần xuất hiện đầu tiên của mỗi ký tự duy nhất
các bước giải quyết
- Chúng tôi tạo một bảng băm freqCount để lưu trữ từng ký tự duy nhất làm khóa và tần số của chúng dưới dạng giá trị
- Chúng tôi tạo một bảng băm khác firstIndex để lưu trữ từng ký tự duy nhất làm khóa và chỉ mục đầu tiên của chúng trong chuỗi đầu vào dưới dạng giá trị
Chúng tôi duyệt tuyến tính chuỗi đầu vào cho từng ký tự S[i]
- Nếu nó tồn tại trong freqCount, chúng tôi tăng số lượng tần số của nó lên 1
- Nếu nó không tồn tại trong freqCount, chúng tôi chèn nó với tần số đếm 1 và chèn nó vào bảng băm firstIndex làm giá trị
Bây giờ chúng tôi làm theo một quy trình tương tự được sử dụng trong phương pháp trước
- Chúng tôi tạo danh sách freq[] giống như các phương pháp trên bằng cách sử dụng Bảng băm freqCount và firstIndex
- Chúng tôi sắp xếp danh sách freq[] dựa trên số lượng ký tự tần suất trong khi duy trì thứ tự ổn định
- Chúng tôi trích xuất các ký tự từ danh sách freq[] đã sắp xếp và lưu trữ nó trong một mảng đầu ra bổ sung result[n]
- Cuối cùng, chúng tôi trả về mảng result[] làm đầu ra
Mã giải pháp C++
phân tích giải pháp
Giả sử có m ký tự duy nhất trong chuỗi đầu vào
Độ phức tạp thời gian = Độ phức tạp thời gian lưu trữ bảng băm freqCount và firstIndex + Độ phức tạp thời gian lưu trữ giá trị trong freq[] + Độ phức tạp thời gian sắp xếp freq[] + Độ phức tạp thời gian lưu trữ đầu ra trong mảng result[] = O[n] + O[n
Độ phức tạp của không gian = Không gian bổ sung của bảng băm freqCount và firstIndex + Không gian bổ sung của danh sách freq[] + Không gian bổ sung của mảng result[] + Không gian sắp xếp bổ sung = 2*O[m] + O[m] + O[n] +
Lưu ý quan trọng. Chúng tôi khuyên bạn nên chuyển đổi các mã giả ở trên thành ngôn ngữ lập trình yêu thích [Java, Python, v.v. ] và xác minh tất cả các trường hợp thử nghiệm. Thích lập trình
Ý tưởng quan trọng để suy nghĩ
- Làm thế nào để chúng tôi giải quyết vấn đề trên nếu không có ràng buộc để duy trì thứ tự được sắp xếp ổn định?
- Làm cách nào để chúng tôi triển khai thuật toán sắp xếp được sử dụng trong các phương pháp trên? . Vì vậy, làm cách nào chúng ta có thể sắp xếp bất kỳ đầu vào nào như vậy theo độ phức tạp thời gian O[n]?
- Chúng ta có thể giải quyết vấn đề này bằng một số cách tiếp cận khác không?
- Làm cách nào để chúng tôi sửa đổi ý tưởng trên để sắp xếp các ký tự theo thứ tự tần suất tăng dần?
- Chúng ta có thể cố gắng giải quyết vấn đề này mà không sử dụng thêm dung lượng không?
- Khám phá một số vấn đề mà chúng tôi sử dụng hai bảng băm cho giải pháp
- So sánh BST và Bảng băm. Trong kịch bản nào chúng ta thích BST hơn bảng băm?
- Trong cách tiếp cận thứ 2. tại sao chúng tôi trích xuất các phần tử từ BST và lưu trữ chúng trong danh sách freq[]?
- Hãy nghĩ về kịch bản khác mà chúng ta có thể lưu trữ các chi tiết bổ sung trong các nút BST để giải quyết vấn đề
Các vấn đề được đề xuất để giải quyết
- Thực hiện các hoạt động xóa tối thiểu sao cho tất cả các phần tử có tần số duy nhất
- Tìm phần tử xuất hiện nhiều nhất trong một mảng
- Tìm tổng tất cả các phần tử có tần số chẵn
- Sắp xếp mảng trừ các phần tử có tần số k
Vui lòng viết vào tin nhắn bên dưới nếu bạn thấy có điều gì không đúng hoặc bạn muốn chia sẻ thông tin chi tiết hơn hoặc bạn biết một số cách tiếp cận khác nhau để giải quyết vấn đề này. Thích học, Thích thuật toán