Подмножества leetcode - Ввод в arr, похоже, неправильно вводит неправильные индексы

#javascript #algorithm

Вопрос:

Работал над этим вопросом с литкодом: https://leetcode.com/problems/subsets/

и придумал это решение:

INPUT = [1, 2, 3]

 
var subsets = function(nums) {
    
    let ans = []
    
    for (let num of nums) {
        
        // DUPLICATE ARRAY
        ans = [...ans, ...ans]
        const size = ans.length
        
        // ITERATE THROUGH LAST HALF OF ARR
        for (let i = size / 2; i < size; i  ) {
            ans[i].push(num) <------------- THIS AINT RIGHT :(
        }
        
        ans.push([num])
    }
    
    return [[], ...ans]
};

ANS = [[],[1,2,3,3],[1,2,3,3],[2,3],[1,2,3,3],[1,2,3,3],[2,3],[3]] (INCORRECT)

Однако по какой-то причине он, похоже, неправильно вставлял значения в несколько индексов. После возни с кодом, думая, что моя логика верна, я пришел к следующему:

 var subsets = function(nums) {
    
    let ans = []
    
    for (let num of nums) {
        
        // DUPLICATE ARRAY
        ans = [...ans, ...ans]
        const size = ans.length
        
        for (let i = size / 2; i < size; i  ) {
            ans[i] = [...ans[i], num] <--------------- THIS WORKS
        }
        
        ans.push([num])
    }
    
    return [[], ...ans]
};


ANS = [[],[1],[1,2],[2],[1,3],[1,2,3],[2,3],[3]] (correct)

И это в конечном итоге сработало… Почему это происходит? arr[i].push(num) В значительной степени это не то же самое, что arr[i] = [...arr[i], num]

1. Я временно удалил свой ответ, потому что нам нужно знать ваши данные (пожалуйста, включите их в сам вопрос). И я сосредоточился на вопросе о том, почему push это не эквивалентно, а не для того, чтобы ответить на реальный вызов 🙂

2. Это не работает. Вот почему я так растерян. ans = [[0], [1], [2]] . Так что это было бы дублированием ans = [[0], [1], [2], [0], [1], [2]] . Поэтому, повторяя вторую половину, push должен правильно нажимать… но это не так…

3. Входные данные [1, 2, 3]

4. Входные данные таковы nums = [0, 1, 2] . Желаемый результат таков [[],[1],[1,2],[2],[1,3],[1,2,3],[2,3],[3]] . Вы можете видеть, что после каждого цикла я нажимаю [num] на ans arr

5. Да, теперь я понимаю, что ты делаешь, @sssyn.

Ответ №1:

Причина в том, что подмассивы не копируются, когда вы это делаете:

     ans = [...ans, ...ans]

Это просто создает одни и те же ссылки на подмассивы. Это означает , что когда вы push перейдете к одному из подмножеств во второй половине ans , вы увидите эффект также и в первой половине ans , поскольку обе половины ссылаются на одни и те же подмножества.

Поэтому, чтобы решить эту проблему, сделайте более глубокую копию при создании второй половины:

     ans = [...ans, ...ans.map(arr => Array.from(arr))]

Вторая, рабочая версия, выполняет эту более глубокую копию в строке, которую вы отметили.