Program JavaScript untuk mencetak semua tiga kali ganda membentuk AP dalam tatasusunan yang disusun

AP ialah jujukan aritmetik di mana perbezaan antara dua unsur berturutan sentiasa sama. Kami akan mencetak semua tiga kali ganda dalam tatasusunan diisih yang membentuk AP menggunakan tiga kaedah: kaedah naif, kaedah carian binari dan kaedah dua penunjuk.

Pengenalan kepada masalah

Dalam soalan ini, kami mendapat tatasusunan tersusun, yang bermaksud semua elemen berada dalam bentuk yang semakin meningkat. Kita perlu mencari tiga elemen dalam tatasusunan dan membentuk AP. Contohnya -

Tatasusunan yang diberikan: 1 5 2 4 3

Daripada tatasusunan yang diberikan, kita mempunyai dua tiga kali ganda: 1 2 3 dan 5 4 3 kerana perbezaan antara unsur bersebelahan adalah sama. Selain itu, seperti yang ditulis, kita hanya perlu mencari tiga kali ganda, jadi kita tidak menemui sebarang jujukan lagi.

Mari beralih kepada kaedah mencari tiga kali ganda -

Kaedah

Kaedah naif

Dalam kaedah ini kita hanya bergerak ke atas tatasusunan menggunakan gelung dan untuk setiap lelaran kita akan menjalankan tatasusunan lain untuk nombor yang lebih besar berbanding dengan indeks semasa. Kemudian kami akan melaksanakan tatasusunan bersarang sekali lagi dalam tatasusunan bersarang pertama untuk mencari elemen yang boleh membentuk AP. Mari lihat kod -

Contoh

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         for(var k = j+1; k < n; k++){
            if(arr[j] - arr[i] == arr[k] - arr[j]) {
               console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + arr[k]);
            }
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

Kerumitan masa kod di atas ialah O(), dengan N ialah saiz tatasusunan.

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

Ikut cara mudah

Dalam kaedah sebelumnya, apabila kita mempunyai dua elemen, kita boleh mencari elemen ketiga kerana kita mempunyai perbezaan yang sama, jadi untuk mencari elemen ketiga, daripada menggunakan carian linear, kita boleh menggunakan carian binari dan Mengurangkan kerumitan masa kod di atas -

Contoh

// function for binary search 
var binarySearch = function (arr, x, start, end) {
   if (start > end) return false;
   var mid=Math.floor((start + end)/2);
   if (arr[mid]===x) return true;
   if(arr[mid] > x)
      return binarySearch(arr, x, start, mid-1);
   else
      return binarySearch(arr, x, mid+1, end);
}
// function to find all the tripletes 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         // third element will be
         var third = 2*arr[j]-arr[i];
         if(binarySearch(arr,third,j+1,n)){
            console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + third);
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

Kerumitan masa kod di atas ialah O(), dengan N ialah saiz tatasusunan.

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

Kaedah yang cekap

Dalam kaedah ini kita akan menggunakan dua penunjuk dan mencari elemen yang mempunyai perbezaan yang sama dengan kedudukan semasa. Mari lihat kod -

Contoh

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   
   // traversing over the array
   for(var i = 1; i< n;i++)    {
      var bptr = i-1
      var fptr = i+1
      while(bptr >= 0 && fptr < n)        {
         if(arr[i] - arr[bptr] == arr[fptr] - arr[i]){
            console.log("Triplet is: " + arr[bptr] + " " + arr[i] + " " + arr[fptr]);
            bptr--;
            fptr++;
         }
         else if(arr[i] - arr[bptr] > arr[fptr] - arr[i]){
            fptr++;
         }
         else{
            bptr--;
         }
      }
   }
}

// defining the array and calling the function 
arr = [1, 4, 7, 10, 13, 16]
findAP(arr)

Kerumitan masa kod di atas ialah O(N*N), dengan N ialah saiz tatasusunan yang diberikan, dan kerumitan ruang bagi kaedah di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan. p>

NOTA - Dua kaedah pertama adalah sah untuk mana-mana jenis tatasusunan yang diisih atau tidak diisih, tetapi kaedah terakhir hanya untuk tatasusunan yang diisih, jika tatasusunan tidak diisih kita boleh mengisih kaedahnya, tetapi kaedah ini masih yang terbaik antara semua yang lain.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program JavaScript untuk mencetak semua tiga kali ganda membentuk AP dalam tatasusunan diisih yang diberikan. Ap ialah janjang aritmetik di mana perbezaan antara dua unsur berturut-turut sentiasa sama. Kami telah melihat tiga kaedah: kaedah naif dengan kerumitan masa O(N*N*N), kaedah carian binari dengan kerumitan masa O(N*N*log(N)), dan kaedah dua penuding.

Atas ialah kandungan terperinci Program JavaScript untuk mencetak semua tiga kali ganda membentuk AP dalam tatasusunan yang disusun. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!