Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

android — Phỏng vấn - Tìm các cực cường độ trong một mảng

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 02:38:38 29 4
mua khóa gpt4 Nike

Cực: Một phần tử trong mảng trong đó phần tử bên trái nhỏ hơn hoặc bằng nó và phần tử bên phải lớn hơn hoặc bằng nó.

Ví dụ đầu vào

3,1,4,5,9,7,6,11

đầu ra mong muốn

4,5,11

Tôi đã được hỏi câu hỏi này trong cuộc phỏng vấn. Để trả về chỉ mục của phần tử, chỉ phần tử đầu tiên đáp ứng điều kiện mới được trả về.

logic của tôi

  1. Lấy hai MultiSet (Để chúng ta cũng có thể xem xét trùng lặp), một cho phía bên phải của phần tử và một cho phía bên trái của phần tử (cực).
  2. Bắt đầu với phần tử thứ 0 và đặt tất cả các phần tử còn lại vào "bộ bên phải".
  3. Điều kiện cơ bản nếu phần tử thứ 0 này nhỏ hơn hoặc bằng tất cả phần tử trên "bộ bên phải" thì trả về chỉ mục của nó.
  4. Ngược lại, đặt phần này vào "bộ bên trái" và bắt đầu với phần tử ở chỉ mục 1.
  5. Duyệt qua mảng và mỗi lần chọn giá trị lớn nhất từ ​​"bộ bên trái" và giá trị tối thiểu từ "bộ bên phải" và so sánh.
  6. Tại bất kỳ thời điểm nào đối với bất kỳ phần tử nào, tất cả giá trị ở bên trái của nó đều nằm trong "bộ bên trái" và giá trị ở bên phải của nó đều nằm trong "bộ bên phải"

mã số

int độPole (const vector &A) {  
   multiset trái, phải;        
   int left_max, right_min;          
   kích thước int = A.size();
   cho (int i = 1; i < size; ++i)
       right.insert(A[i]);
   right_min = *(right.begin()); 
   if(A[0] <= right_min)
       return 0;
   left.insert(A[0]);
   for (int i = 1; i < size; ++i) {
       right.erase(right.find(A[i]));
       left_max = *(--left.end());
       nếu (right.size() > 0)
           right_min = *(right.begin());
       if (A[i] > left_max && A[i] <= right_min)
           trả lại tôi;
       khác
           left.insert(A[i]);
   }
   return -1;
}

câu hỏi của tôi

  • Tôi được thông báo rằng logic của tôi không chính xác, tôi không thể hiểu tại sao logic này không chính xác (mặc dù tôi đã kiểm tra một số trường hợp và nó đang trả về đúng chỉ mục)
  • Vì sự tò mò của riêng tôi về cách thực hiện việc này mà không cần sử dụng bất kỳ bộ/nhiều bộ nào trong thời gian O(n).

câu trả lời hay nhất

Đối với thuật toán O(n):

  1. Tính phần tử lớn nhất từ ​​n[0] đến n[k] cho mọi k trong [0,length(n)) và lưu kết quả vào mảng maxOnTheLeft. Chi phí này O(n);
  2. Với tất cả k trong [0, length(n)], hãy tính phần tử nhỏ nhất từ ​​n[k] đến n[length(n)-1] và lưu câu trả lời vào mảng minOnTheRight. Chi phí này O(n);
  3. Hãy thực hiện toàn bộ quá trình và tìm bất kỳ n[k] nào mà maxOnTheLeft <= n[k] <= minOnTheRight. Chi phí này là O (n).

Mã của bạn (ít nhất) sai ở đây:

if (A[i] > left_max && A[i] <= right_min) // <-- nên là >= và <=

Về thuật toán - phỏng vấn - tìm cực biên độ trong một mảng, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/15397637/

29 4 0
Bài viết khuyến nghị: Thứ tự thẻ HTML5
Bài viết khuyến nghị: android — Cách so sánh một phần hai biểu đồ
Bài viết khuyến nghị: php - liên kết ngoài không có http|https bị lỗi
Bài viết khuyến nghị: Big O đại diện cho thời gian chạy trong trường hợp xấu nhất và Ω đại diện cho trường hợp tốt nhất, nhưng tại sao đôi khi Ω lại được sử dụng cho trường hợp xấu nhất?
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress