BastterCode semana 17 - 88. Merge Sorted Array

Tecnologia
FlyCavok   180º
em 19/06/23 23:49
Nível no Race: Tá começando a andar
ver comentários do moderador

Comentários

Último comentário 1º comentário do autor Só moderadores Só os meus Só quem eu sigo Ordenar por gostei
Giovanni 
em 20/06/2023 21:04
Nível no Race: Profissa do Bastter Race
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
        int i = m - 1;
        int j = n -1;
        int k = m + n - 1;

        while(i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        while (j >=0) {
            nums1[k]= nums2[j];
            j--;
            k--;
        }
}

os loops começam de trás para frente dos dois arrays usando os dados m e n que repreentam o tamanho preenchido de cada array, e colocando o maior número no array "mergeado" nums1 final cujo tamanho é m+n

o segundo é para pegar as sobras do nums2, se houver


BastterCode semana 17 - 88. Merge Sorted Array - #1 de 5
FlyCavok  180º
em 20/06/2023 21:47
Nível no Race: Tá começando a andar


postado por @Giovanni em 20/06/2023 21:04
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
        int i = m - 1;
        int j = n -1;
        int k = m + n - 1;

        while(i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        while (j >=0) {
            nums1[k]= nums2[j];
            j--;
            k--;
        }
}


os loops começam de trás para frente dos dois arrays usando os dados m e n que repreentam o tamanho preenchido de cada array, e colocando o maior número no array "mergeado" nums1 final cujo tamanho é m+n

o segundo é para pegar as sobras do nums2, se houver


Boa, fez em o(m+n) !
BastterCode semana 17 - 88. Merge Sorted Array - #2 de 5
oxe  1º
em 21/06/2023 14:09 
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if (n == 0) return;
        if (m == 0) {
            nums1 = move(nums2); 
            return;
        }
        
        while (n > 0) {            
            unsigned short end = m + n - 1;
            
            if (m == 0 || nums1[m - 1] <= nums2[n - 1])
                    nums1[end] = nums2[--n];
            else
                    nums1[end] = nums1[--m];
        }
    }
};


Primeiro verifico se o segundo vetor é nulo, caso em que o merge é simplesmente o primeiro vetor e posso interromper o programa.

Depois, verifico se o primeiro vetor é nulo, caso em que o merge é o segundo. Como o programa espera que o merge esteja contido no primeiro vetor, uso um move para atribuir o conteúdo do segundo vetor ao primeiro em O(1) e depois interrompo o programa.

Nos demais casos, vou percorrendo ambos os vetores elemento a elemento de trás pra frente, selecionando o maior e inserindo na traseira do primeiro vetor. Se já analisei todos os elementos do primeiro vetor, o loop continua inserindo os elementos restantes do segundo vetor até o fim. Se já cheguei ao fim do segundo vetor, não há mais elementos a inserir e o programa termina.
BastterCode semana 17 - 88. Merge Sorted Array - #3 de 5
shadow_walker  180º
em 29/06/2023 17:56
Nível no Race: Na Tonga da Mironga do Kabuletê
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i = 0
        while i < n: nums1[m + i], i = nums2[i], i + 1
        nums1.sort()


Olhando de cara o desafio, pensei que iria encontrar dificuldade. No entanto, achei bem fácil de implementar em Python.
BastterCode semana 17 - 88. Merge Sorted Array - #4 de 5
shadow_walker  180º
em 29/06/2023 18:19
Nível no Race: Na Tonga da Mironga do Kabuletê
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        nums1[m:] = nums2[:]
        nums1.sort()


Outra solução melhor ainda: sem usar um loop, mas apenas alterando o array nums1 com "fatiamento".
BastterCode semana 17 - 88. Merge Sorted Array - #5 de 5

4 usuários comentaram este tópico.
Clique para ir para o primeiro comentário do usuário.