Keadaan Tatasusunan Akhir Selepas Operasi Darab K I

3264. Keadaan Tatasusunan Akhir Selepas Operasi Darab K I

Kesukaran: Mudah

Topik: Tatasusunan, Matematik, Timbunan (Baris Gilir Keutamaan), Simulasi

Anda diberi nombor tatasusunan integer, integer k dan pengganda integer.

Anda perlu melakukan operasi k pada nombor. Dalam setiap operasi:

• Cari nilai minimum x dalam nombor. Jika terdapat berbilang kejadian nilai minimum, pilih yang muncul dahulu.
• Gantikan nilai minimum x yang dipilih dengan x * pengganda.

Kembalikan susunan integer yang menandakan keadaan akhir nombor selepas melakukan semua operasi k.

Contoh 1:

• Input: nombor = [2,1,3,5,6], k = 5, pengganda = 2
• Output: [8,4,6,5,6]
• Penjelasan:

| Operasi | Keputusan |
|-------------------|-----------------|
| Selepas operasi 1 | [2, 2, 3, 5, 6] |
| Selepas operasi 2 | [4, 2, 3, 5, 6] |
| Selepas operasi 3 | [4, 4, 3, 5, 6] |
| Selepas operasi 4 | [4, 4, 6, 5, 6] |
| Selepas operasi 5 | [8, 4, 6, 5, 6] |

Contoh 2:

• Input: nombor = [1,2], k = 3, pengganda = 4
• Output: [16,8]
• Penjelasan:

| Operasi | Keputusan |
|-------------------|-----------------|
| Selepas operasi 1 | [2, 2, 3, 5, 6] |
| Selepas operasi 2 | [4, 2, 3, 5, 6] |
| Selepas operasi 3 | [4, 4, 3, 5, 6] |
| Selepas operasi 4 | [4, 4, 6, 5, 6] |
| Selepas operasi 5 | [8, 4, 6, 5, 6] |

Kekangan:

• 1
• 1
• 1
• 1

Petunjuk:

1. Kekalkan pasangan diisih (bilangan[indeks], indeks) dalam baris gilir keutamaan.
2. Simulasikan operasi sebanyak k kali.

Penyelesaian:

Kita perlu melaksanakan operasi seperti yang diterangkan dalam pernyataan masalah. Langkah utama ialah mencari nilai minimum dalam tatasusunan, menggantikannya dengan nilai yang didarab dengan pengganda yang diberikan, dan kemudian ulangi proses ini sebanyak k kali.

Memandangkan kita perlu memilih kejadian pertama nilai minimum dan menggantikannya, kita boleh mendekati ini dengan menjejaki indeks nilai minimum semasa setiap operasi. Pelaksanaan PHP akan menggunakan baris gilir keutamaan (min-timbunan) untuk mendapatkan semula dan mengemas kini nilai minimum dengan cekap semasa setiap operasi.

Mari laksanakan penyelesaian ini dalam PHP: 3264. Keadaan Tatasusunan Akhir Selepas Operasi Darab K I

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $multiplier
 * @return Integer[]
 */
function finalArrayState($nums, $k, $multiplier) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$nums1 = [2, 1, 3, 5, 6];
$k1 = 5;
$multiplier1 = 2;
$result1 = finalArrayState($nums1, $k1, $multiplier1);
echo "Output: [" . implode(", ", $result1) . "]\n";

// Test Case 2
$nums2 = [1, 2];
$k2 = 3;
$multiplier2 = 4;
$result2 = finalArrayState($nums2, $k2, $multiplier2);
echo "Output: [" . implode(", ", $result2) . "]\n";
?>

Penjelasan:

1. Permulaan: Gelung k kali kerana anda perlu melakukan operasi k.
2. Cari Nilai Minimum:
   • Lelaran ke atas nombor tatasusunan untuk mencari nilai terkecil dan indeks kejadian pertamanya.
3. Darab Nilai Minimum:
   • Gantikan nilai pada indeks yang dikenal pasti dengan hasil darab nilai semasa dan pengganda.
4. Ulang:
   • Ulang langkah di atas untuk k lelaran.
5. Kembalikan Tatasusunan Akhir:
   • Kembalikan tatasusunan yang diubah suai selepas semua operasi.

Keluaran Ujian

Untuk kes ujian yang disediakan:

Kes Ujian 1:

Input:

$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

Output:

Output: [8, 4, 6, 5, 6]

Kes Ujian 2:

Input:

$nums = [1, 2];
$k = 3;
$multiplier = 4;

Output:

Output: [16, 8]

Kerumitan

1. Kerumitan Masa:

   • Untuk setiap operasi k, mencari nilai minimum dalam tatasusunan memerlukan O(n).
   • Jumlah: O(k x n), dengan n ialah saiz tatasusunan.

2. Kerumitan Angkasa:

   • Penyelesaian menggunakan O(1) ruang tambahan.

Penyelesaian ini mematuhi kekangan dan memberikan hasil yang diharapkan untuk semua kes ujian.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Keadaan Tatasusunan Akhir Selepas Operasi Darab K I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!