Chương trình Javascript để tìm số lớn thứ hai và nhỏ thứ hai trong một mảng

Thí dụ

Chúng ta hãy xem xét một số ví dụ được cung cấp để tìm phần tử lớn thứ hai trong mảng

ví dụ 1. Mảng đầu vào đã cho là {12, 35, 1, 10, 34, 1} Đầu ra. Phần tử lớn thứ hai trong mảng là 34

ví dụ 2. Mảng đầu vào đã cho là {10, 5, 10} Đầu ra. Phần tử lớn thứ hai trong mảng là 5

ví dụ 3. Mảng đầu vào đã cho là {10, 10, 10} Đầu ra. không áp dụng. [Không có phần tử lớn thứ hai trong mảng đã cho, vì vậy chúng tôi không thể tìm thấy số lớn thứ hai trong mảng. ]

Giải thích ví dụ

Trước khi đi vào giải thích cách tìm phần tử lớn thứ hai trong mảng, trước tiên chúng ta hãy giới thiệu sơ qua về mảng

Mảng là một tập hợp tuyến tính các giá trị được lưu trữ tại các vị trí bộ nhớ liền kề. Mảng lưu trữ các giá trị đồng nhất [giá trị kiểu dữ liệu tương tự]

Một số điểm quan trọng cần lưu ý về mảng như sau

• Các mảng chiếm không gian liên tục [tiếp giáp] trong bộ nhớ
• Việc lập chỉ mục của mảng bắt đầu bằng 0 và tiếp tục đến [độ dài của mảng - 1]
• Mảng có độ dài cố định, i. e. sau khi tạo mảng, chúng ta không thể thay đổi kích thước của mảng
• Việc truy cập các phần tử rất nhanh trong mảng. Chúng ta có thể dễ dàng truy cập bất kỳ phần tử nào bằng cách sử dụng chỉ mục của mảng

Thí dụ. Mảng os 56, 50, 34, 24, 12 sẽ như thế nào

Để tìm hiểu thêm về mảng, tham khảo bài viết - Mảng trong cấu trúc dữ liệu

Hạn chế

• Đầu vào đầu tiên là số phần tử có trong mảng i. e. N
• Đầu vào thứ hai là tập hợp tuần tự các phần tử của mảng

Trong một số bài toán, bạn có thể thấy số ca kiểm thử được biểu thị bằng t. Vì vậy, chúng ta chỉ cần gọi hàm đảo ngược t-lần

Vấn đề là tìm phần tử lớn thứ hai trong mảng

Cách tiếp cận 1 [Giải pháp đơn giản]

Hãy để chúng tôi tìm hiểu cách tiếp cận đơn giản hoặc vũ phu để tìm phần tử lớn thứ hai trong mảng. Một trong những giải pháp đơn giản nhất có thể là sắp xếp mảng theo thứ tự tăng dần rồi tìm phần tử thứ hai không bằng phần tử lớn nhất trong mảng đã sắp xếp. Vì vậy, theo cách này, chúng ta có thể tìm thấy phần tử lớn thứ hai trong mảng

Mã giả có thể là

1. Sort the array in ascending order.
2. Find the second element which is not equal to the largest element from the sorted array.
C++
#include 
using namespace std;

int findSecondLargest[int a[], int n]
{
   /*
   First, sort the array and find the first_largest element present in the array [at the last position].
   */
   sort[a, a + n];

   /*
   Now for the second_largest element, we need to start from second last element as the largest element is at last.
   */
   int second_largest = 0;
   for [int i = n - 2; i >= 0; i--]
   {
      /*
      If the last and second last element are equal then check the previous one else return the second last element.
      */
      if [a[i] != a[n - 1]]
      {
         second_largest = a[i];
         break;
      }
   }

   return second_largest;
}

int main[]
{
   int a[] = {12, 35, 1, 10, 34, 1};
   int n = sizeof[a] / sizeof[a[0]];

   int answer = findSecondLargest[a, n];

   cout = 0; i--] {
    if [a[i] != a[n - 1]] {
      second_largest = a[i];
      break;
    }
  }

  return second_largest;
}

const a = [12, 35, 1, 10, 34, 1];
let n = a.length;
let answer = findSecondLargest[a, n];
console.log["The second largest element in the array is: " + answer];
con trăn
def find_second_largest[a, n]:
    """
    First, sort the array and find the first_largest element present in the array [at the last position].
    """
    a.sort[]

    """
    Now for the second_largest element, we need to start from second last element as the largest element is at last.
    """
    second_largest = 0

    for i in range[n-2, -1, -1]:
        """
        If the last and second last element are equal then check the previous one else return the second last element.
        """
        if a[i] != a[n - 1]:
            second_largest = a[i]
            break

    return second_largest


if __name__ == '__main__':
    a = [12, 35, 1, 10, 34, 1]
    n = len[a]
    answer = find_second_largest[a, n]
    print["The second largest element in the array is: ", answer]
đầu ra

  

The second largest element in the array is:  34
Phân tích độ phức tạp
Trong cách tiếp cận đơn giản này để tìm phần tử lớn thứ hai trong mảng, trước tiên chúng ta sắp xếp mảng mất thời gian O[log n]. Ngoài ra, chúng tôi không sử dụng thêm bất kỳ khoảng trống nào ngoài một biến cụ thể là second_dest để lưu trữ và trả về câu trả lời
Thời gian phức tạp
Độ phức tạp về thời gian của cách tiếp cận trên để tìm số lớn thứ hai trong mảng là O[n log[n]], trong đó n là số phần tử có trong mảng
Độ phức tạp không gian
Độ phức tạp không gian của cách tiếp cận trên là O[1]

Cách tiếp cận 2 [Giải pháp tốt hơn]

Hãy để chúng tôi tìm hiểu một cách tiếp cận tốt hơn nhưng đơn giản hơn để tìm phần tử lớn thứ hai trong mảng. Một trong những giải pháp cơ bản hoặc đơn giản nhất có thể là chạy hai vòng lặp. Vòng lặp đầu tiên sẽ tìm phần tử lớn nhất đầu tiên trong mảng [giả sử first_most là phần tử lớn nhất có trong mảng]. Sau đó, vòng lặp thứ hai sẽ tìm phần tử lớn nhất có trong mảng nhỏ hơn first_large. Vì vậy, theo cách này, chúng ta có thể tìm thấy phần tử lớn thứ hai trong mảng

Mã giả có thể là

1. Find the largest element in the array and store its value [let's say first_largest].
2. Find the largest element in the array which is smaller than first_largest and return the value found.
C++
#include 
using namespace std;

int findSecondLargest[int a[], int n]
{
   /*
   Let us assume that initially, the largest element [first_largest] present in the array is INT_MIN.
   */
   int first_largest = INT_MIN;

   /*
   The first loop will find the first_largest element present in the array.
   */
   for [int i = 0; i < n; i++]
   {
      /*
      Update the value of first_largest if the current element is larger than the first_largest value till now.
      */
      if [first_largest < a[i]]
      {
         first_largest = a[i];
      }
   }

   /*
   Now find the largest element present in the array which is smaller than the first_largest.

   Initially, the second element present in the array is INT_MIN.
   */

   int second_largest = INT_MIN;
   for [int i = 0; i < n; i++]
   {
      if [a[i] > second_largest and a[i] < first_largest]
      {
         second_largest = a[i];
      }
   }

   return second_largest;
}

int main[]
{
   int a[] = {12, 35, 1, 10, 34, 1};
   int n = sizeof[a] / sizeof[a[0]];

   int answer = findSecondLargest[a, n];

   cout = 0; i--]
   {
      /*
      If the last and second last element are equal then check the previous one else return the second last element.
      */
      if [a[i] != a[n - 1]]
      {
         second_largest = a[i];
         break;
      }
   }

   return second_largest;
}

int main[]
{
   int a[] = {12, 35, 1, 10, 34, 1};
   int n = sizeof[a] / sizeof[a[0]];

   int answer = findSecondLargest[a, n];

   cout