Jadual Kandungan
Kaedah 2
Algoritma
Contoh
Output
Rumah pembangunan bahagian belakang C++ Kurangkan tatasusunan kepada paling banyak satu elemen dengan operasi yang diberikan

Kurangkan tatasusunan kepada paling banyak satu elemen dengan operasi yang diberikan

Aug 29, 2023 pm 02:25 PM
Operasi tatasusunan mengurangkan elemen

Kurangkan tatasusunan kepada paling banyak satu elemen dengan operasi yang diberikan

Dalam masalah ini, kami mengurangkan saiz tatasusunan kepada 1 atau 0 dengan melakukan operasi yang diberikan setiap pusingan.

Kita boleh mengisih tatasusunan dalam setiap pusingan untuk mendapatkan elemen maksimum dalam setiap lelaran. Selain itu, kami juga boleh menggunakan struktur data kepala untuk meningkatkan prestasi kod.

Pernyataan Masalah - Kami diberi pelbagai nombor[]. Kita perlu mengurangkan tatasusunan dengan melakukan perkara berikut.

  • Pilih dua elemen terbesar dalam tatasusunan.

  • Jika dua elemen adalah sama, padamkan dua elemen daripada tatasusunan.

  • Jika dua elemen tidak sama, padamkan dua elemen daripada tatasusunan dan masukkan abs(pertama − sekunder) ke dalam tatasusunan.

Cetak elemen terakhir tatasusunan. Jika tatasusunan kosong, cetak 0.

Contoh

Masuk

nums = {5, 9, 8, 3, 2, 5};
Salin selepas log masuk

Output

0
Salin selepas log masuk

Arahan

  • Dalam pusingan pertama, kami mengambil 9 dan 8 dan menambah perbezaannya pada tatasusunan. Oleh itu, tatasusunan menjadi [5, 3, 2, 5, 1].

  • Dalam pusingan kedua kami mengambil 5 dan 5. Oleh itu, tatasusunan menjadi [3, 2, 1].

  • Pusingan seterusnya, kita ambil 3 dan 2. Oleh itu, tatasusunan menjadi [1, 1]

  • Dalam pusingan terakhir, kami mengambil 1 dan 1. Oleh itu, tatasusunan menjadi kosong dan kami mencetak 0.

Masuk

nums = {5, 5, 5, 5, 5};
Salin selepas log masuk

Output

5
Salin selepas log masuk

Penjelasan- Kami memadamkan sepasang 5 dua kali, dan satu 5 kekal dalam tatasusunan.

Masuk

nums = {4, 8, 7, 6};
Salin selepas log masuk

Output

1
Salin selepas log masuk

Penjelasan - Mula-mula, kami pilih 8 dan 7. Oleh itu, tatasusunan menjadi [4, 1, 6]. Selepas itu, kita pilih 4 dan 6. Oleh itu, tatasusunan menjadi [1, 2]. Pada operasi terakhir, tatasusunan menjadi [1].

Kaedah 1

Dalam kaedah ini, kita akan melelar melalui tatasusunan sehingga saiz tatasusunan menjadi 1 atau 0. Dalam setiap lelaran, kami akan mengisih tatasusunan dan melaksanakan operasi yang diberikan pada 2 elemen pertama tatasusunan yang diisih. Akhir sekali, kami akan mencetak output berdasarkan saiz tatasusunan.

Algoritma

Langkah 1- Simpan saiz tatasusunan dalam pembolehubah "len".

Langkah 2- Mula melintasi tatasusunan menggunakan gelung sementara.

Langkah 3- Gunakan kaedah sort() dalam gelung untuk membalikkan menyusun tatasusunan.

Langkah 4- Dapatkan elemen pertama dan kedua tatasusunan. Juga, hitung perbezaan antara elemen pertama dan kedua tatasusunan.

Langkah 5− Jika perbezaannya ialah 0, padamkan dua elemen pertama tatasusunan dan kurangkan 'len' sebanyak 2. Jika perbezaannya bukan 0, padamkan 2 elemen pertama dan tolak 'len' tolak 1.

Langkah 6- Akhir sekali, jika saiz tatasusunan ialah 0, kembalikan 0. Jika tidak, elemen pertama tatasusunan dikembalikan.

Contoh

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    int len = nums.size();
    int p = 0;
    while (len > 1) {
        // Sort array in reverse order
        sort(nums.begin(), nums.end(), greater<int>());
        // Take the first and second elements of the array
        int a = nums[0];
        int b = nums[1];
        // Take the difference between the first and second element
        int diff = a - b;
        if (diff == 0) {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            len -= 2;
        } else {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            nums.push_back(diff);
            len -= 1;
        }
    }
    // When the size of the array is 0
    if (nums.size() == 0)
        return 0;
    return nums[0];
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}
Salin selepas log masuk

Output

The last remaining element after performing the given operations is 0
Salin selepas log masuk
Salin selepas log masuk

Kerumitan masa - O(N*NlogN), di mana O(N) digunakan untuk lelaran ke atas tatasusunan dan O(NlogN) digunakan untuk mengisih tatasusunan dalam setiap lelaran.

Kerumitan ruang - O(N) untuk mengisih tatasusunan.

Kaedah 2

Dalam kaedah ini, kami akan menggunakan baris gilir keutamaan, yang melaksanakan struktur data timbunan. Ia sentiasa menyimpan elemen dalam susunan yang disusun. Jadi kita boleh mengalih keluar 2 elemen terbesar pertama dengan mudah.

Algoritma

Langkah 1- Takrifkan "p_queue" yang dipanggil priority queue.

Langkah 2- Masukkan semua elemen tatasusunan ke dalam baris gilir keutamaan.

Langkah 3- Ulang sehingga saiz baris gilir keutamaan lebih besar daripada 1.

Langkah 4- Padamkan 2 elemen pertama barisan keutamaan satu demi satu.

Langkah 5- Cari perbezaan antara dua elemen.

Langkah 6- Jika perbezaannya bukan 0, tolak ke barisan keutamaan.

Langkah 7− Akhir sekali, jika saiz giliran ialah 0, kembalikan 0.

Langkah 8- Jika tidak, kembalikan elemen di bahagian atas baris gilir.

Contoh

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    // Defining a priority queue
    priority_queue<int> p_queue;
    // Inserting array elements in priority queue
    for (int p = 0; p < nums.size(); ++p)
        p_queue.push(nums[p]);
    // Make iterations
    while (p_queue.size() > 1) {
        // Take the first element from queue
        int first = p_queue.top();
        p_queue.pop();
        // Get the second element from queue
        int second = p_queue.top();
        p_queue.pop();
        // Take the difference of first and second elements
        int diff = first - second;
        if (diff != 0)
            p_queue.push(diff);
    }
    // When queue is empty
    if (p_queue.size() == 0)
        return 0;
    // Return the last remaining element
    return p_queue.top();
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}
Salin selepas log masuk

Output

The last remaining element after performing the given operations is 0
Salin selepas log masuk
Salin selepas log masuk

Kerumitan masa - Kerumitan masa untuk memasukkan dan memadam elemen dalam baris gilir keutamaan ialah O(NlogN).

Kerumitan Ruang - O(N) untuk menyimpan elemen dalam baris gilir keutamaan.

Struktur data baris gilir keutamaan sentiasa berguna apabila kita perlu menyusun data tatasusunan dalam susunan tertentu selepas memasukkan atau memadam sebarang elemen. Ia melaksanakan struktur data timbunan, dengan itu membolehkan pemasukan dan pemadaman.

Atas ialah kandungan terperinci Kurangkan tatasusunan kepada paling banyak satu elemen dengan operasi yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Mar 03, 2025 pm 05:52 PM

Butiran artikel ini C jenis pulangan fungsi, merangkumi asas (int, float, char, dan lain -lain), diperolehi (tatasusunan, petunjuk, struktur), dan jenis kekosongan. Pengkompil menentukan jenis pulangan melalui pengisytiharan fungsi dan pernyataan pulangan, menguatkuasakan

Gulc: Perpustakaan C dibina dari awal Gulc: Perpustakaan C dibina dari awal Mar 03, 2025 pm 05:46 PM

GULC adalah perpustakaan C berprestasi tinggi yang mengutamakan overhead yang minimum, inlining agresif, dan pengoptimuman pengkompil. Sesuai untuk aplikasi kritikal prestasi seperti perdagangan frekuensi tinggi dan sistem tertanam, reka bentuknya menekankan kesederhanaan, modul

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu Mar 03, 2025 pm 05:53 PM

Artikel ini menerangkan perisytiharan fungsi C vs definisi, argumen lulus (dengan nilai dan penunjuk), nilai pulangan, dan perangkap umum seperti kebocoran memori dan jenis ketidakcocokan. Ia menekankan pentingnya pengisytiharan modularity dan provi

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Mar 03, 2025 pm 05:53 PM

Butiran artikel ini C berfungsi untuk penukaran kes rentetan. Ia menerangkan menggunakan ToUpper () dan Tolower () dari CType.H, meleleh melalui rentetan, dan mengendalikan terminator null. Perangkap biasa seperti melupakan ctype.h dan mengubahsuai literal rentetan adalah

Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Mar 03, 2025 pm 05:51 PM

Artikel ini mengkaji fungsi penyimpanan nilai pulangan C. Nilai pulangan kecil biasanya disimpan dalam daftar untuk kelajuan; Nilai yang lebih besar boleh menggunakan petunjuk untuk memori (timbunan atau timbunan), memberi kesan kepada seumur hidup dan memerlukan pengurusan memori manual. Secara langsung acc

Penggunaan dan perkongsian frasa yang berbeza Penggunaan dan perkongsian frasa yang berbeza Mar 03, 2025 pm 05:51 PM

Artikel ini menganalisis kegunaan pelbagai kata sifat "berbeza," meneroka fungsi tatabahasa, frasa umum (mis., "Berbeza," "berbeza"), dan aplikasi bernuansa dalam formal vs tidak formal

Bagaimanakah saya menggunakan algoritma dari STL (jenis, mencari, mengubah, dll) dengan cekap? Bagaimanakah saya menggunakan algoritma dari STL (jenis, mencari, mengubah, dll) dengan cekap? Mar 12, 2025 pm 04:52 PM

Artikel ini memperincikan penggunaan algoritma STL yang cekap dalam c. Ia menekankan pilihan struktur data (vektor vs senarai), analisis kerumitan algoritma (mis., Std :: Sort vs Std :: partial_sort), penggunaan iterator, dan pelaksanaan selari. Perangkap biasa seperti

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Mar 12, 2025 pm 04:50 PM

Artikel ini menerangkan Perpustakaan Templat St Standard (STL), yang memberi tumpuan kepada komponen terasnya: bekas, iterator, algoritma, dan functors. Ia memperincikan bagaimana ini berinteraksi untuk membolehkan pengaturcaraan generik, meningkatkan kecekapan kod dan kebolehbacaan t

See all articles