Program Javascript untuk pertanyaan julat kekerapan elemen tatasusunan

Kami mendapat tatasusunan yang mengandungi integer dan tatasusunan lain yang mengandungi pertanyaan, setiap pertanyaan yang kami wakili diberikan oleh indeks paling kiri dan paling kanan serta elemen dalam tatasusunan daripada julat. Untuk julat atau subarray itu, kita perlu mencari kekerapan elemen tertentu dalam julat itu berlaku.

Kekerapan unsur bermakna kita perlu memberitahu setiap integer yang terdapat dalam julat berapa kali ia berlaku. Contohnya -

Jika, tatasusunan yang diberikan ialah: [5, 2, 5, 3, 1, 5, 2, 2, 5]

Susun pertanyaan ialah: [[0, 4, 5], [1, 7, 2]]

• Untuk pertanyaan pertama, subarray ialah: 5, 2, 5, 3, 1, jadi kekerapan 5 ialah 2.

• Untuk pertanyaan kedua, subarray ialah 2, 5, 3, 1, 5, 2 dan 2, jadi kekerapan 2 ialah 3.

kaedah

Untuk menyelesaikan isu ini, kami akan mengikuti langkah berikut -

• Pertama, kami akan mencipta fungsi berasingan untuk memanggil setiap pertanyaan dan menghantar elemen pertanyaan sebagai parameter.

• Di dalam fungsi kita akan mendapat panjang tatasusunan untuk diulang dan mencipta kiraan pembolehubah untuk menyimpan kekerapan elemen yang diberikan.

• Kami akan menggunakan gelung for untuk lelaran ke atas julat yang diberikan dan pada setiap lelaran, jika elemen tatasusunan semasa adalah sama dengan elemen yang diberikan, kami akan menambah kiraan.

• Akhir sekali, kami akan mencetak kiraan semasa bagi elemen yang diberikan.

Contoh

Mari lihat kod yang betul untuk melaksanakan langkah di atas untuk pemahaman yang lebih baik -

// function to answer their queries 
function findFre(arr, L, R, ele ){
   var n = arr.length 
   var count = 0
   // traversing over the array 
   for(var i = L; i <= R; i++){
      if(arr[i] == ele){
         count++;
      }
   }
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(Q*N), dengan Q ialah bilangan pertanyaan dan N ialah saiz tatasusunan. Kerumitan masa ialah faktor N kerana untuk setiap pertanyaan kami mengulangi tatasusunan dalam julat yang diberikan.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan untuk menyimpan apa-apa.

Keadaan istimewa

Dalam kod di atas, kita mendapat kerumitan masa O(Q*N), jika bilangan elemen berbeza yang terdapat dalam tatasusunan yang diberikan adalah kurang daripada bilangan tatasusunan berasingan untuk setiap elemen, kita boleh mengira ruang mengikut Kerumitan untuk meningkatkan kerumitan masa atau untuk mengekalkan pemetaan jumlah awalan.

Tetapi kaedah ini menggunakan banyak ruang dan kerumitannya ialah O(D*N), di mana D ialah bilangan elemen berbeza yang terdapat dalam tatasusunan dan N ialah panjang tatasusunan.

Dengan mengekalkan jumlah awalan, jawapan kepada sebarang pertanyaan boleh diberikan dalam masa O(1), dan kerumitan masa keseluruhan ialah O(Q), dengan Q ialah bilangan pertanyaan.

Contoh

var store = null;
function lb(a, l, h, k){
   if (l > h){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k <= a[m]) {
      return lb(a, l, m - 1, k);
   }
   return lb(a, m + 1, h, k);
}
function ub(a, l, h, k){
   if (l > h || l == a.length){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k >= a[m]){
      return ub(a, m + 1, h, k);
   }
   return ub(a, l, m - 1, k);
}
function findFre(arr, L, R, ele){
   var n = arr.length
   var left_side = lb(store.get(ele), 0, store.get(ele).length, L);
   var right_side = ub(store.get(ele), 0, store.get(ele).length, R);
   var count = right_side - left_side;
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
// creating a map to store the elements 
store = new Map();
for (var i = 0; i < arr.length; i++){
   if (!store.has(arr[i])){
      store.set(arr[i],new Array());
   }
   store.get(arr[i]).push(i);
}
// creating map for the different elements
// defining queries array 
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

KESIMPULAN

Dalam tutorial ini, kami melaksanakan program JavaScript untuk menjawab pertanyaan julat untuk menjawab kekerapan elemen tertentu dalam julat yang disediakan dalam setiap pertanyaan. Kami telah mengulangi julat yang diberikan dalam tatasusunan dan mengekalkan pembolehubah untuk mendapatkan kiraan. Kerumitan masa kod di atas ialah O(Q*N), dan kerumitan ruang bagi kod di atas ialah O(1).

Atas ialah kandungan terperinci Program Javascript untuk pertanyaan julat kekerapan elemen tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!