J'ai trouvé Question similaire à propos de l'entrelacement de deux arraylistes en un, mais c'est en php. On m'a demandé cette question en interview aussi bien mais ne pouvais pas le résoudre, je suis revenu à regarder si elle était déjà traitée, mais je ne pouvais trouver que ceci papier
de sorte que tous les pointeurs de pseudo-code ou de la définition de la méthode?
grosse (o) restrictions: O (n) - Coût de temps et O (1) - Coût de l'espace
exemple:
A [] = A1, A2, ..., un
B [] = B1, B2, ..., BN
Réorganiser le tableau à A1, B1, A2, B2, ..., A, BN editv1.0 : ArrayListes A [] et B [] ont de la même taille
editv2.0 : Et si la question est étendue à réorganiser dans l'une des deux tableaux donnés, mais ne crée pas un nouveau tableau?
6 Réponses :
Pour la simplicité, supposez que les matrices ont la même longueur et sont des tableaux int code>. int[] merge(int[] a, int[] b)
{
assert (a.length == b.length);
int[] result = new int[a.length + b.length];
for (int i=0; i<a.length; i++)
{
result[i*2] = a[i];
result[i*2+1] = b[i];
}
return result;
}
@Matt c'est vrai, mais si je devais fusionner dans l'une des deux tableaux, mais pas créer un nouveau tableau?
Vous ne pouvez pas faire cela à moins que vous soyez prêt à exclure la moitié des éléments de chaque tableau d'entrée, car les tableaux ne peuvent pas être redimensionnés.
@Matt Vous avez des arraylistes à Java, qui peuvent nous aider à augmenter la taille?
Oui, mais c'est une liste, pas un tableau, et j'aurais utilisé un code complètement différent dans ce cas.
Aahh, j'ai étiqueté la question sous Java pensé que vous envisageriez que les listes achetent par défaut.
@Superman peut-être que vous pourriez coller la moitié des éléments entrelacés de l'un des matrices d'origine et de la moitié des éléments entrelacés de l'autre tableau d'origine, mais je ne vois pas comment cela pourrait être fait dans O (n).
@mlaw: avec des tableaux réellement assez faciles, il s'agit simplement d'échanger des éléments entre les deux tableaux.
@Matt c'est ce que je pensais, au début. Mais cela ne semble pas être le cas. Entrelacement [1 2 3 4 5] and [6 7 8 9 0]: Vous commenceriez d'abord à remplacer 2 avec 6 conduits au remplacement de 3 avec 2 et 5 avec 3 et 9 avec 5 et ainsi de suite. Ensuite, vous devez remplacer 4 avec 7 et propager ces remplaces.
@mlaw Soins Pour poster vos idées comme réponse?
@mlaw Cela dépend de l'entrelacement exact que vous visez dans la deuxième matrice. Pour interlaisser les deux tableaux x = [1, 2, 3, 4, 5] et y = [A, B, C, D] Vous pouvez créer < Code> x '= [1, B, 3, D, 5] et Y' = [A, 2, C, 4, D] . Tu vois ce que je veux dire?
@Matt ouais, dans ce cas, ce serait simple.
@Matt: Créer X 'et Y' n'est pas O (1) espace, est-ce? Je suis d'accord avec Mlaw. Sans créer de nouveaux tableaux / étendre les originaux, cela semble difficile. Le document relié à la question pourrait y être utile.
@user: x ' et y' ne serait pas de nouveaux tableaux, j'ai utilisé le "Prime" pour indiquer qu'ils ont été des versions modifiées de l'original.
@Matt: Alors, comment feriez-vous l'échange? Soins à élaborer? Choisissez des tableaux de 12 éléments chacun par exemple. N'oubliez pas que la contrainte de mémoire supplémentaire O (1). Remarque: je parle de x '= [1 A 2 B 3], Y' = [C 4 D 5 E]. (Je viens de réaliser que vous parlez d'un autre entrelacement, désolé pour cela).
BTW, je ne vois pas de point dans l'entrelacement comme vous l'avez fait :-) Pourquoi ne pas simplement laisser les tableaux comme ils sont?
Je pense que les opérations mod (%) de la réponse de Matt sont incorrectes. Sous la même hypothèse (que les matrices sont la même longueur), je proposerais la solution suivante à la place:
static int[] merge(final int[] a, final int[] b)
{
final int[] result = new int[a.length * 2];
for (int i=0; i < a.length; i++)
{
result[i << 1] = a[i];
result[(i << 1) + 1] = b[i];
}
return result;
}
Oups - on dirait que Matt corrige son exemple aussi. Ils sont essentiellement équivalents maintenant.
Je pense que cela n'est pas faisable avec vos contraintes données ( Si vous avez deux listes liées, ceci est faisable - si nous supposons que le collecteur des ordures est assez rapide, c'est-à-dire supprimer un élément d'une liste et l'ajout à une autre liste ne casse pas la limitation de l'espace. Cette méthode fonctionne pour une paire de listes, mais n'est que O (N) pour être lié. Listes. Pour une liste liée personnalisée où nous pouvons modifier les pointeurs, nous n'avons pas à compter sur le collecteur des ordures, nous changerons simplement les nœuds. Ici pour une liste individuellement liée: pour une liste doublement liée, nous devrions également adapter les pointeurs PREV-POINTS. Ici le Variante d'emballage mentionnée dans le premier paragraphe: ceci est en réalité O (n) heure et O (1) espace, c'est-à-dire aucun espace supplémentaire) pour un tableau ou une matrice -La liste des dépenses. (En supposant bien sûr, que nous ne pouvons pas simplement créer un nouvel objet de la liste déléguant aux originaux.) o (1) à temps, aussi.
J'ai fait une petite solution en supposant que vous parlez d'utiliser le tableau (voir mon commentaire sur la question). Je peux trop simplifier le problème sur la base de certaines des réponses ici, mais voilà quand même.
L'exemple ci-dessous prend A et B de type peu importe ce qui se passe si vous combinez les arraylistes que vous combinez " Je vais avoir deux fois la taille. ArrayList selon votre modification v2.0.
Les listes ne doivent pas nécessairement avoir la même taille: pour tester ceci:
Je trouve votre manque de déclarations d'affirmation dérangeantes.
Hein? Vous parlez-vous aux relevés d'asserts Junit? Ce sont des "tests" destinés à démontrer. Utilisez-vous vraiment des méthodes "principales ()" lorsque vous souhaitez démontrer? -1 à ce sujet.
Je n'utilise pas de tests à démontrer; J'affirme un comportement à leur place. En un sens, les tests démontrent si mes assertions sont valables ou non. Mais un test JUNIT sans aucune affirmation est ... dérangeant.
dans l'intervalle de Lambda a été introduit
O (n) complexité du temps
O (1) complexité de l'espace
Est-ce que "
O (1) coût de l'espace" moyenne "o (1) en plus dans l'espace nécessaire pour stocker les deux tableaux?" Quel est le comportement attendu lorsque les deux tableaux n'ont pas la même taille?@Matt oui votre droite, édité ma question sur la taille des tableaux.
Oh, BTW, ce papier n'a essentiellement rien à voir avec votre question.
Eh bien, il a été attaché à l'une des questions similaires, mais la question était de réarranger dans les 2 tableaux donnés mais ne crée pas de nouveau tableau.
Vous utilisez le tableau des termes et la flaylist interchangeables et les deux réponses jusqu'à présent traitent des tableaux. Quelle structure la question a-t-elle posé sur?
Si nous avons un tableau [A1 A2 ... un B1 B2 .. Bn] au lieu de deux, je crois que le document est pertinent. Ou même si l'entrelacement résultant est censé ressembler à un = [A1 B1 A2 B2 ... A (N / 2) B (N / 2)], B = [A (N / 2 + 1) B (N / 2 + 1) ... un bn].
Trouvé une vieille question Stackoverflow Question: Stackoverflow.com/Questtions/1777901/Array-InterLeaving-Probl Em
@ user127.0.0.1 Il n'y a pas de mise en œuvre appropriée dans cette question
@mckarthy son arraylist
@Superman: votre question est contradictoire. Vous voulez réorganiser dans un tableau mais utilisez uniquement O (1) espace? Êtes-vous sûr de votre question?
Oui je suis sûr de o (1) espace