JavaScript mảng tròn

Mảng mà phần tử tiếp theo của phần tử cuối cùng là phần tử đầu tiên của mảng thường được gọi là mảng

Rõ ràng là không tồn tại cơ chế lưu trữ dữ liệu như thế này, dữ liệu vẫn sẽ được lưu trữ trong các khối bộ nhớ liên tục và mảng tròn giống như một ý tưởng hơn là thực tế

Vấn đề

Chúng ta được yêu cầu viết một hàm JavaScript nhận một mảng tròn các Số nguyên, arr, làm đối số đầu tiên và duy nhất

Sau đó, hàm sẽ xây dựng và trả về một mảng chứa phần tử lớn hơn tiếp theo cho từng phần tử tương ứng của mảng ban đầu. Số lớn hơn tiếp theo của một số, giả sử num, là số lớn hơn đầu tiên theo thứ tự duyệt của nó (đúng trong trường hợp của chúng ta) tiếp theo trong mảng, có nghĩa là chúng ta có thể tìm kiếm theo vòng tròn để tìm số lớn hơn tiếp theo của nó. Nếu điều đó không tồn tại, chúng ta nên xem xét -1 cho số này

Ví dụ: nếu đầu vào của hàm là -

const arr = [7, 8, 7];

Sau đó, đầu ra phải là -

const output = [8, -1, 8];

Giải thích đầu ra

Tiếp theo lớn hơn cho cả hai số 7 trong mảng là 8 và vì mảng là hình tròn nhưng đối với 8, không có phần tử nào lớn hơn do đó chúng tôi đặt -1 cho nó

Thí dụ

Mã cho điều này sẽ là -

Bản thử trực tiếp

const arr = [7, 8, 7];
const nextGreaterElement = (arr = []) => {
   const res = [];
   const stack = [];
   if (!arr || arr.length < 1){
      return res;
   };
   for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
         const small = stack.pop();
         res[small] = arr[i];
      };
      stack.push(i);
   }
   for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
         const small = stack.pop();
         res[small] = arr[i];
      };
   }
   const rem = stack.length;
   for (let i = 0; i < rem; i++) {
      res[stack.pop()] = -1;
      }
      return res;
   };
console.log(nextGreaterElement(arr));

Giải thích mã

Trong khi lặp lại mảng nếu chúng tôi tìm thấy một phần tử lớn hơn một phần tử trong ngăn xếp, chúng tôi đặt res[small] thành phần tử lớn hơn hiện tại được tìm thấy

Bây giờ, chúng ta lại bắt đầu từ đầu mảng và xử lý các phần tử mà chúng ta không thể tìm thấy phần tử lớn hơn tiếp theo trong vòng lặp for trước đó. Cuối cùng, vẫn sẽ có một số phần tử mà không có phần tử lớn hơn tiếp theo

Cấu trúc dữ liệu mảng tròn đơn giản, để lưu trữ danh sách giá trị có độ dài hữu hạn và tự động loại bỏ các giá trị không còn phù hợp với mảng. Tất cả các hoạt động là O(1)

Cách sử dụng

npm install --save circular-array

// ES6
import { CircularArray } from 'circular-array';
 
// CommonJS
const { CircularArray } = require('circular-array');
 
const gizmos = new CircularArray(3);



 
                     // gizmo.array() returns:
gizmos.push(gizmo1); //   [gizmo1]
gizmos.push(gizmo2); //   [gizmo1, gizmo2]
gizmos.push(gizmo3); //   [gizmo1, gizmo2, gizmo3]
gizmos.push(gizmo4); //   [gizmo4, gizmo2, gizmo3]

Mảng tròn trong Javascript là gì?

Làm thế nào chúng ta có thể xác định một mảng tròn?

Tại sao sử dụng mảng tròn để triển khai hàng đợi lại có lợi?

Mảng là gì [