Diberi tatasusunan, tulis program PHP untuk mengira bilangan pasangan terbalik saiz tiga

Pengiraan bawah ialah kaedah pengiraan langkah di mana kita boleh mengira bilangan langkah pengisihan yang dilakukan untuk tatasusunan tertentu. Ia juga dapat mengira jangka masa operasi tatasusunan. Tetapi jika kita ingin mengisih tatasusunan dengan cara yang bertentangan, kiraan akan menjadi bilangan maksimum yang terdapat dalam tatasusunan.

Array: { 5, 4, 3, 2, 1}  // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5}  // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5  

Kiraan penyongsangan mewakili jarak tatasusunan tertentu itu daripada diisih dalam tertib menaik. Berikut ialah dua prosedur khusus yang menerangkan situasi ini dengan penyelesaian -

• Untuk mencari elemen yang lebih kecil - Untuk mencari elemen yang lebih kecil daripada tatasusunan, kita perlu mengulangi indeks daripada n-1 kepada 0. Dengan menggunakan (a[i]-1), kita boleh mengira getSum() di sini. Proses akan berjalan sehingga mencapai a[i]-1.

• Untuk mencari nombor yang lebih besar - Untuk mencari nombor yang lebih besar daripada indeks, kita perlu melakukan lelaran 0 hingga n-1. Bagi setiap elemen, kita perlu mengira setiap nombor sehingga a[i]. Tolak daripada i. Kemudian kita akan mendapat nombor yang lebih besar daripada a[i].

Algoritma untuk mengira penyongsangan saiz 3 dalam tatasusunan:-

Dalam algoritma ini; kita belajar cara mengira penyongsangan saiz 3 dalam tatasusunan tertentu dalam persekitaran pengaturcaraan tertentu.

• Langkah 1 - Mulakan

• Langkah 2 - Isytiharkan tatasusunan dan terbalikkan kiraan (seperti arr[] --> tatasusunan dan invCount --> terbalikkan kiraan)

• Langkah 3 - Gelung dalam y=x+1 hingga N

• Langkah 4 - Jika elemen pada x lebih besar daripada elemen pada indeks y

• Langkah 5 - Kemudian tingkatkan invCount++

• Langkah 6 - Cetak pasangan

• Langkah 7 - Penamatan

Sintaks untuk mengira penyongsangan saiz 3 dalam tatasusunan: -

Sepasang (A[i], A[j]) dikatakan berada dalam keadaan songsang jika syarat berikut dipenuhi: A[i] > A[j] dan i < j< j

Pelaksanaan C++

int getInversions(int * A, int n) {
   int count = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         if (A[i] > a[j]) {
            ++count;
         }
      }
   }
  return count;
}

Pelaksanaan Java

public static int getInversions(int[] A, int n) {
  int count = 0;
 
  for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (A[i] > A[j]) {
            count += 1;
         }
 
      }
   }
  return count;
}

Pelaksanaan Python

def getInversions(A, n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if A[i] > A[j]:
                count += 1
 
   return count;
}

Pelaksanaan PHP

<?php
$a=array("a "=>"Volvo","b"=>"BMW","c"=>"Toyota");
print_r(array_reverse($a));
?>

Di sini kami menyebut sintaks yang mungkin untuk mengira penyongsangan saiz 3 dalam tatasusunan yang diberikan. Untuk kaedah ini; kerumitan masa: O(N^2), dengan N ialah jumlah saiz kerumitan ruang: O(1), kerana tiada ruang tambahan digunakan.

Kaedah untuk diikuti:-

• Kaedah 1 - Kira pembalikan saiz 3 dalam tatasusunan yang diberikan mengikut atur cara untuk mengira pembalikan saiz 3

• Kaedah 2 - Cara yang lebih baik untuk mengira penyongsangan saiz 3

• Kaedah 3 - Kira pembalikan saiz 3 menggunakan pokok indeks binari

Kira pembalikan saiz 3 dalam tatasusunan yang diberikan mengikut atur cara untuk mengira pembalikan saiz 3

Untuk cara mudah mengira penyongsangan saiz 3, kita perlu menjalankan gelung untuk semua kemungkinan nilai i, j dan k. Kerumitan masa ialah O(n^3), dan O(1) mencerminkan ruang tambahan.

Syaratnya ialah:

a[i] > a[j] > a[k] dan i < j < k. < j < k。

Contoh 1

<?php
function getInvCount($arr, $n){
	$invcount = 0;

	for ($i = 1; $i < $n - 1; $i++){
		$small = 0;
		for($j = $i + 1; $j < $n; $j++)
			if ($arr[$i] > $arr[$j])
				$small++;
		$great = 0;
		for($j = $i - 1; $j >= 0; $j--)
			if ($arr[$i] < $arr[$j])
				$great++;
		$invcount += $great * $small;
	}

	return $invcount;
}
	$arr = array(16, 7, 22, 10);
	$n = sizeof($arr);
	echo "Inversion Count : "
		, getInvCount($arr, $n);
?>

Output

Inversion Count : 0

Cara yang lebih baik untuk mengira penyongsangan saiz 3

Dalam kaedah ini, kami menganggap setiap elemen tatasusunan sebagai elemen tengah terbalik. Ia membantu mengurangkan kerumitan. Untuk pendekatan ini, kerumitan masa ialah O(n^2) dan ruang tambahan ialah O(1).

Contoh 2

<?php
function getInvCount($arr, $n){
	$invcount = 0;

	for ($i = 1; $i < $n - 1; $i++){
		$small = 0;
		for ($j = $i + 1; $j < $n; $j++)
			if ($arr[$i] > $arr[$j])
				$small++;
		$great = 0;
		for ($j = $i - 1; $j >= 0; $j--)
			if ($arr[$i] < $arr[$j])
				$great++;
		$invcount += $great * $small;
	}

	return $invcount;
}

$arr = array (81, 14, 22, 7);
$n = sizeof($arr);
echo "Inversion Count For The Input Is : " ,
	getInvCount($arr, $n);

?>

Output

Inversion Count For The Input Is : 2

Kira penyongsangan saiz 3 menggunakan pokok indeks binari

Dalam kaedah ini kami juga mengira elemen yang lebih besar dan elemen yang lebih kecil. Kemudian lakukan pendaraban [] dan lebih kecil [] dan tambahkannya pada hasil akhir. Kerumitan masa di sini ialah O(n*log(n)), dan ruang tambahan dinyatakan sebagai O(n).

Contoh 3

<?php
function getInvCount($arr, $n) {
	$invcount = 0;

	for ($i = 1; $i < $n - 1; $i++){
		$small = 0;
		for ($j = $i + 1; $j < $n; $j++)
			if ($arr[$i] > $arr[$j])
				$small++;
		$great = 0;
		for ($j = $i - 1; $j >= 0; $j--)
			if ($arr[$i] < $arr[$j])
				$great++;
		$invcount += $great * $small;
	}

	return $invcount;
}
$arr = array (811, 411, 16, 7);
$n = sizeof($arr);
echo "Inversion Count After The Process : " ,
	getInvCount($arr, $n);
?>

Output

Inversion Count After The Process : 4

Kesimpulan

Dalam artikel ini, kita akan melihat cara mengira penyongsangan saiz 3 dalam tatasusunan yang diberikan. Mudah-mudahan, melalui artikel ini dan kod yang disebutkan menggunakan bahasa tertentu, anda telah mendapat pemahaman yang luas tentang subjek tersebut.

Atas ialah kandungan terperinci Diberi tatasusunan, tulis program PHP untuk mengira bilangan pasangan terbalik saiz tiga. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!