Rumah  >  Artikel  >  Java  >  Set kuasa

Set kuasa

DDD
DDDasal
2024-09-19 06:19:33454semak imbas

Power set

Masalah

Pendekatan menjejak ke belakang:
TC:(2^n) iaitu kerumitan masa eksponen (Memandangkan kita ditinggalkan dengan dua pilihan pada setiap panggilan rekursif iaitu sama ada untuk mempertimbangkan nilai pada 'indeks' atau tidak yang membawa kepada 2 kemungkinan hasil, ini akan berlaku untuk n kali)
SC:(2^n)*(n), n untuk temp ArrayList<>() dan 2^n untuk ArrayList utama<>();

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        powerSet(nums,0,list,new ArrayList<Integer>());
        return list;
    }
    public void powerSet(int [] nums, int index , List<List<Integer>> list, List<Integer> l){
        //base case
        if(index ==nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        //take
        l.add(nums[index]); //consider the value at 'index'
        powerSet(nums,index+1,list,l);
        //dont take;
        l.remove(l.size()-1);// don't consider the value at 'index'
        powerSet(nums,index+1,list,l);
    }
}

Menggunakan Manipulasi Bit:
TC: O(2^n)*n
SC: O(2^n)*n, (2^n untuk senarai utama dan n untuk senarai subset, bukan semua subset akan bersaiz n tetapi kita masih boleh menganggap begitu)

pra-syarat: semak sama ada bitnya ditetapkan atau tidak (rujuk halaman petua dan helah manipulasi Bit untuk butiran lanjut)
Intuisi:
Jika semua tidak. subset diwakili sebagai nilai binari,
contohnya : jika n = 3 iaitu tatasusunan yang mempunyai 3 nilai di dalamnya.
akan ada 2^n = 8 subset
8 subset juga boleh diwakili sebagai

index 2 index 1 index 0 subset number
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7

Kami akan mengambil kira bahawa jika nilai bit ialah 1 maka nilai indeks dalam nums[] harus diambil kira untuk membentuk subset.
Dengan cara ini kita akan dapat mencipta semua subset

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length;
        int noOfSubset = 1<<n; // this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets

        for(int num = 0;num<noOfSubset;num++){ /// all possible subsets numbers
            List<Integer> l = new ArrayList<>();
            for(int i =0;i<n;i++){// for the given subset number find which index value to pick 
                if((num & (1<<i))!=0) l.add(nums[i]); 
            }
            list.add(l);
        }
        return list;
    }
}

Atas ialah kandungan terperinci Set kuasa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
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