[C/C++] Tìm số lớn thứ 2 trong mảng (1 for)

Hôm nay định tiếp tục series về lập trình hướng đối tượng trong C++, chợt nhớ đến bài toán hay được hỏi trong các buổi phóng vấn, nên cũng muốn chia sẻ chút cho đổi gió.

Bài toán đặt ra:

Tìm số lớn thứ 2 trong mảng số nguyên.

Bài toán nghe chừng rất đơn giản. Ta dùng 2 vòng lặp:

  • Vòng lặp thứ nhất tìm ra số lớn nhất.
  • Vòng lặp thứ 2 tìm ra số lớn thứ 2.

Done! Ta đã tìm ra được kết quả.

Nhưng nếu bài toán yêu cầu thêm 1 chút là chỉ dùng 1 vòng lặp thì sao?

Suy nghĩ 1 lúc. Khó quá anh ơi, thôi chào anh em về, đợt sau tìm được cách giải quyết em đến phỏng vấn tiếp. Về tra google thấy trên DEEP-CPP có bài viết chia sẻ về bài toán đó. Chưa biết đúng sai, hay dở thế nào cứ đọc đã:

Bước 1 : 2 max thì mình dùng 2 biến để lưu giá trị.

  • Max1 : Lưu giá trị lớn nhất.
  • Max2 : Lưu giá trị lớn thứ 2.

Ta gán

  • Max1 cho phần tử đầu tiên của mảng.
  • Max2 ta gán cho 1 số rất rất nhỏ.
Max1 = arr[0];

Max2 = INT32_MIN;

Bước 2 : Duyệt mảng từ phần tử thứ 2 (trừ phần tử đầu đã gán cho Max1) đến cuối mảng để tìm số lớn thứ 2.

Quan điểm về số lớn thứ 2:

  • QD1 : 1 2 3 4 5 5 => Số lớn thứ 2 là 5.
  • QD2 : 1 2 3 4 5 5 => Số lớn thứ 2 là 4.

Trong bài này mình sẽ in ra kết quả theo QD2. Nếu các phần tử bằng nhau hết, hay mảng chỉ có 1 phần tử thì sẽ là không có phần tử lớn thứ 2 và in ra “No Max 2”;

Trong vòng lặp ta kiểm tra:

if (arr[i] > Max1)
{
    Max2 = Max1;
    Max1 = arr[i];
}
else if (arr[i] > Max2 && arr[i] < Max1)
{
    Max2 = arr[i];
}

Nếu muốn in ra kết quả theo QD1 ta chỉ cần  thay đổi 1 chút trong điều kiện.

if (arr[i] > Max1)
{
    Max2 = Max1;
    Max1 = arr[i];
}
else if (arr[i] > Max2)
{
    Max2 = arr[i];
}

Bước 3 : In ra kết quả

if (Max2 == INT32_MIN)
{
    cout << "No Max 2" << endl;
}
else
{
    cout << "Max 2 = " << Max2 << endl;
}

Tham khảo code đầy đủ

#include <iostream>

using namespace std;

int main()

{

   int* arr = nullptr;

   int n, Max1, Max2;

   cout << "Enter array number n = ";
	
   cin >> n;

   arr = new int[n];

   cout << "Enter array value : " << endl;

   for (int i = 0; i < n; i++)

   {

      cin >> arr[i];

   }

   Max1 = arr[0];

   Max2 = INT32_MIN;

   for (int i = 1; i < n; i++)

   {
 
      if (arr[i] > Max1)

      {

         // Gán max1 cho max2
         Max2 = Max1;

         // Cập nhập lại giá trị max2
         Max1 = arr[i];

      }

      else if (arr[i] > Max2 && arr[i] < Max1)

      {

         //Cập nhập giá trị max2
         Max2 = arr[i];

      }

   }

   cout << "Max 1 = " << Max1 << endl;

   if (Max2 == INT32_MIN)

   {

      cout << "No Max 2" << endl;

   }

   else

   {

      cout << "Max 2 = " << Max2 << endl;

   }
	
   delete[] arr;

   return 0;

}

Hi vọng các bạn khi đi phỏng vấn gặp phải vấn đề này không còn bị lúng túng. Có thể còn nhiều cách giải nữa các bạn comment bên dưới để cùng thảo luận nhé. Hoặc tham gia nhóm facebook của DEEP-CPP theo link bên dưới đề cùng thảo luận.

Có 3 bình luận

  1. Lam

    Một cách khác mk muốn đề ra: so sánh 2 số đầu để gán Max1,Max2.

  2. vmt

    nếu max1 mà đứng đầu mảng thì code trên sai sao ấy.
    vd : 9 6 5 1 thì nó in ra 9 9 chứ ko in ra 9 6

Leave A Comment?