Tìm Phần Tử Lớn Nhất Trong Mảng C++

Bài Toán: Cho một mảng có kích thước N, nhiệm vụ là tìm phần tử lớn nhất trong mảng đã cho.

Ví Dụ:

Input: arr[] = {10, 20, 4}
Output: 20

Input : arr[] = {20, 10, 20, 4, 100}
Output : 100

Phương Pháp 1: Gán Giá Trị MAX và Duyệt Toàn Bộ Danh Sách

Một trong những cách tiếp cận cơ bản và đơn giản nhất để giải quyết vấn đề này là chỉ cần duyệt qua toàn bộ danh sách và tìm giá trị lớn nhất trong số đó.

Thực hiện theo các bước dưới đây để thực hiện thuật toàn này:

Tạo một biến max để lưu trữ giá trị lớn nhất trong danh sách
Khởi tạo max với phần tử đầu tiên đầu tiên của mảng để bắt đầu so sánh.
Sau đó duyệt qua mảng đã cho từ phần tử thứ hai cho đến cuối,với mỗi phần tử:
- So sánh phần tử hiện tại với max
- Nếu phần tử hiện tại lớn hơn giá trị max, thì hãy thay thế giá trị của giá trị max bằng phần tử hiện tại.
Cuối cùng, trả về và in giá trị của phần tử lớn nhất của mảng được lưu trữ trong giá trị tối đa.

Dưới đây là việc thực hiện phương pháp trên:

// C++ program to find maximum
// in arr[] of size n
#include <bits/stdc++.h>
using namespace std;

int largest(int arr[], int n)
{
   int i;
   
   // Initialize maximum element
   int max = arr[0];

   // Traverse array elements
   // from second and compare
   // every element with current max
   for (i = 1; i < n; i++)
      if (arr[i] > max)
         max = arr[i];

   return max;
}

// Driver Code
int main()
{
   int arr[] = {10, 324, 45, 90, 9808};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Largest in given array is "
      << largest(arr, n);
   return 0;
}

// This Code is contributed
// by Shivi_Aggarwal

Output:

Largest in given array is 9808

Độ phức tạp về thời gian: O (N), để duyệt hoàn toàn Mảng.

Phương pháp 2: Giải pháp đệ quy)

Thuật toán sử dụng đệ quy để duyệt mảng và tìm phần tử lớn nhất.

// C++ program to find maximum
// in arr[] of size n
#include <bits/stdc++.h>
using namespace std;

int largest(int arr[], int n, int i)
{
   // last index
   // return the element
   if (i == n - 1) {
      return arr[i];
   }

   // find the maximum from rest of the array
   int recMax = largest(arr, n, i + 1);

   // compare with i-th element and return
   return max(recMax, arr[i]);
}

// Driver Code
int main()
{
   int arr[] = { 10, 324, 45, 90, 9808 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Largest in given array is "
      << largest(arr, n, 0);
   return 0;
}

// This Code is contributed by Rajdeep Mallick

Output:

Largest in given array is 9808

Độ phức tạp thời gian: O (N), trong đó N là kích thước của mảng đã cho.

Phương Pháp 3: Sử Dụng Thư Viện

Sử dụng hàm thư viện: Hầu hết các ngôn ngữ đều có hàm tích hợp kiểu max () có liên quan để tìm phần tử tối đa, chẳng hạn như std :: max_element trong C ++. Chúng ta có thể sử dụng hàm này để tìm trực tiếp phần tử tối đa.

Dưới đây là việc thực hiện phương pháp trên:

// C++ program to find maximum in arr[] of size n
#include <bits/stdc++.h>
using namespace std;

// returns maximum in arr[] of size n
int largest(int arr[], int n)
{
   return *max_element(arr, arr+n);
}

int main()
{
   int arr[] = {10, 324, 45, 90, 9808};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << largest(arr, n);
   return 0;
}

Output:

Độ phức tạp về thời gian: O (N), vì hàm max_element () được tích hợp sẵn mất O (N) thời gian.

The post Tìm Phần Tử Lớn Nhất Trong Mảng C++ first appeared on Techacademy.

source https://techacademy.edu.vn/tim-phan-tu-lon-nhat-trong-mang-c/

Techacademy

Tìm kiếm Blog này