Найти дубликаты в двух массивах


Найти Дубликаты

Даны два упорядоченных массивов arr1 и arr2 из номеров паспортов, реализовать findDuplicates функцию, которая возвращает массив все номера паспортов, которые находятся в arr1 и arr2. Обратите внимание, что выходной массив должен быть отсортирован в порядке возрастания.

Пусть N и M-длины arr1 и arr2, соответственно. Решить для двух случаев и анализировать время и пространство сложности вашего решения: М ≈ Н - длины массива примерно такие же М ≫ Н - arr2 гораздо больше, чем arr1.

Мой подход:

import java.io.*;
import java.util.*;
import java.lang.*;

class Solution {

  static int[] findDuplicates(int[] arr1, int[] arr2) {
    // your code goes here
    int i = 0, j = 0, k = 0;
    ArrayList<Integer> ans = new ArrayList<>();
    while(( i < arr1.length) && (j < arr2.length))
    {
      if(arr1[i] < arr2[j])
          i++;
      else if(arr1[i] == arr2[j])
      {
          ans.add(arr1[i]);
          k++;
          i++;
          j++;
      }
      else
          j++;
     }
    int[] arr = new int[ans.size()];

    for(int l = 0; l < ans.size(); l++) {
    if (ans.get(l) != null) {
        arr[l] = ans.get(l);
    }
}
    return arr;
  }
   //M = arr1.length, N = arr2.length        
  //Time = O(M+N)
  //Space = O(min(M,N))

У меня есть следующие вопросы относительно моего кода:

1) Как я могу улучшить время и сложность пространства мой код?

2) есть ли лучший способ(меньше строк кода, лучше структуры данных), которые могут быть использованы, чтобы улучшить код?

Источник: макет интервью



Комментарии
5 ответов

Я бы сказал, что код страдает читаемость более чем из аспектов эффективности вы (или ваш интервьюер) имел в виду.

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

И в конце концов, это не сказать что-то о ваших навыков, как на Java - программиста. Но это проблема вашего интервьюера...


1) Как я могу улучшить время и сложность пространства мой код?

удаление неиспользуемых переменных будет первым шагом. Вы заявляете и приращения k но вы никогда не читали его. Но согласись, это не "убийца"...


2) есть ли лучший способ(меньше строк кода, лучше структуры данных), которые могут быть использованы, чтобы улучшить код?

Чистый Лок метрика не имеет смысла. Самое важное свойство кода (после правильности) является читабельность. Структурирование кода на небольшие методы с четкими обязанностями и хорошо выбранные имена-это гораздо более высокую ценность, потом Лок, но его то измеримые...

так вот мое предложение. Особенно присмотритесь к содержанию for петли как в описание о моем намерении, что код должен делать:

import java.util.ArrayList;
import java.util.List;
class Solution {
static int[] findDuplicates(int[] arr1, int[] arr2) {
List<Integer> ans = selectDuplicates(//
arr1.length < arr2.length ? arr1 : arr2, // shorter
arr1.length < arr2.length ? arr2 : arr1);// longer
return convertToIntArray(ans);
}

private static List<Integer> selectDuplicates(int[] shorter, int[] longer) {
ArrayList<Integer> duplicates = new ArrayList<>();
int indexInLonger = 0;
for (int current : shorter) {
indexInLonger = seekToEqualOrBiggerIn(longer, current, indexInLonger);
addMatchTo(duplicates, current, longer[indexInLonger]);
}
return duplicates;
}

private static int seekToEqualOrBiggerIn(int[] longer, int current, int indexInLonger) {
while (longer.length > indexInLonger && current > longer[indexInLonger])
indexInLonger++;
return indexInLonger;
}

private static void addMatchTo(ArrayList<Integer> duplicates, int current, int possibleMatch) {
if (current == possibleMatch)
duplicates.add(current);
}

private static int[] convertToIntArray(List<Integer> ans) {
return ans.stream().mapToInt(item -> item.intValue()).toArray();
}
}



selectDuplicates() заставляет абоненту проверить длину массива? – Шарон Бен Ашер

selectDuplicates() это private способ внедрения деталь не предназначены, чтобы быть вызванным кем-либо еще. Так что не абонент "принудительный", чтобы проверить длину.


почему? – Шарон Бен Ашер
Это оптимизация.

Идея заключается в том, что я все делаю быстро, когда я не делаю их.

С этой оптимизацией длина короткой массив неявно проверяется foreach петли. Это избавляет меня от увеличения и проверить, как индексируется во время итерации.

Это также уменьшает количество итераций до размера меньшего массива с большим массивом должны иметь некоторые записи не в меньшем массиве.


это внутренняя реализация, которая имеет смысл только в метод и не вызывающий. – Шарон Бен Ашер

Точно! Thats, почему это я моя реализация не подвергается внешнему воздействию.


и это даже не проверить, если он есть правильные аргументы. – Шарон Бен Ашер

какой бы "правильный" аргумент выглядеть на ваш взгляд?


он должен быть способен принимать любые два массива
разобраться в которых короче, чем. ты смог бы покороче() и больше() методы, которые делают фактическую проверку и selectDuplicates() называть их.... – Шарон Бен Ашер

Метод findDuplicates() которой является общедоступный интерфейс делает именно это.


Мне тоже не нравится название методов. seekToEqualOrBiggerIn() слишком специфичные для реализации.

Но что является главной целью частных методов название: описать текущее поведение этого метода как можно более подробно.


что если вход отсортированных в обратном? уверен, что вам придется изменить код внутри метода, но намерение метода остается прежней: пропустить элементы, которые придется "опустить" того, согласно приказу массивов.
– Шарон Бен Asherand

ОПС требования явно упомянуто в порядке возрастания. По словам YAGNY-principly я не должен предоставить ожидается, но не требуется гибкость. ИМХО это относится и к слишком именования.

В том случае, если требование будет изменить это имя на самом деле легче найти детали, чтобы изменить, а пробегая по коду. Конечно было бы переименовать тогда.


кроме того, addMatchTo() не намек на то, что матч еще не определена и что условие применяется. – Шарон Бен Ашер

По крайней мере для меня это. И нет вопроса: получатель сообщения определяет его содержание.


и я не понимаю причину этой конкретной взламывания кода в методы. почему вы должны findDuplicates() и selectDuplicates() ? это кажется произвольным разделением.

findDuplicates() является частью публичного API (фиксируется интервьюером, я думаю).

Реализация ОПС состоит из двух логических частей:


  1. найти и собрать дубликаты в списке

  2. преобразовать список в массив, как ожидалось подписью методов.

Для меня это две разные обязанности , которые должны жить в собственных методах согласно один принцип ответственности.

Поскольку Java не позволяет методы подписи отличаются только возвращаемым значением мне нужно другое, но похожее название.

2
ответ дан 4 февраля 2018 в 11:02 Источник Поделиться

Вот мои комментарии:


  1. Переменная k было, вероятно, предназначено, чтобы отслеживать размер массива списка (количества копий). Однако он является избыточным, поскольку вы используете списка size() метод.

  2. Чтобы преобразовать список в массив вы можете использовать API поток. хотя я не уверен, если он предоставляет в любое время/космос, это, наверное, самый оптимизированный способ сделать это, и это избавляет вас от необходимости объявлять возвращаемый массив. Так как это сложно сделать преобразование с примитивными типами массивов, вот это: ans.stream().mapToInt(item -> item.intValue()).toArray(); и вы можете сделать его возвращаемым значением метода.

  3. При условие, используя избыточные круглые скобки, которые имеют && между ними . Можно утверждать, как дело вкуса, но на мой взгляд, условие-это четкое и без них. Я добавить дополнительное пространство вокруг высших порядков оператора: while(i < arr1.length && j < arr2.length)

3
ответ дан 4 февраля 2018 в 11:02 Источник Поделиться

Если бы я забил этот код, я хотел бы отметить следующие:


    int i = 0, j = 0, k = 0;

Я бы разделил их на несколько строк. Либо

    int i = 0,
j = 0,
k = 0;

Или я на самом деле предпочитают

    int i = 0;
int j = 0;

Как уже отмечалось k является избыточным.

Я бы только использовать запятые, если я пишу это как for петли.

    for (int i = 0, j = 0; i < arr1.length && j < arr2.length; ) {

Я бы предпочел отдельные высказывания иначе.


    ArrayList<Integer> ans = new ArrayList<>();

Две вещи.

    List<Integer> answer = new ArrayList<>();

Как просто дело привычки, я бы объявить переменную как Тип List. Это не делает большой разницы, но это хорошая привычка есть. Я бы вниз для не имеющих его.

Там, кажется, нет причин сокращать ответ ans. Спасение трех букв теперь против когнитивный диссонанс от того, чтобы разобраться каждый раз, когда кто-то читает это? Я предпочел бы видеть разработчики тратят три буквы. Это в благое дело.


      if(arr1[i] < arr2[j])

Опять две вещи.

      if (arr1[i] < arr2[j]) {

Я предпочитаю всегда использовать пробел между ключевыми словами, такими как if и while и в последующих скобках. Это помогает мне отличать ключевые слова от способ звонков, так что я могу прочитать код быстрее.

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

Это не обязательно плохо. Возможно, кто-то другой станет вместо моей версии. Но я считаю, что мои варианты лучше вписываются в стандарт Java.

3
ответ дан 4 февраля 2018 в 12:02 Источник Поделиться

В дополнение к другим ответы:

Не использовать подстановочные импорта как import java.util.*;. Представьте, что в будущем версии Java, Oracle добавляет класс в java.util пакет, который сталкивается с некоторым классом, который вы уже используете. Тогда вы в конечном итоге с конфликтами имен. Использовать только индивидуальные импорта для отдельных классов.

Импортную как import java.lang.*; показывает отсутствие знаний о Java именования системы. Классы java.lang всегда доступны с простым именем, не нуждаются в импорте заявление.

Итак, ваше решение показывает, что вы получили правильный алгоритм (это хорошо известно, так что не очень трудно), но в Java Новичок и не сильно забочусь о стиле.

Это решение не поможет вам получить работу в качестве Java-разработчика - только в качестве стажера.

3
ответ дан 4 февраля 2018 в 02:02 Источник Поделиться

class Solution {

public static int[] findDuplicates(int[] arr1, int[] arr2) {
if (arr1 == null || arr2 == null) {
throw NPE();
}

int i = 0, j = 0;
final List<Integer> ans = new ArrayList<>();
while((i < arr1.length) && (j < arr2.length)) {
if(arr1[i] < arr2[j]) {
i++;
} else if(arr1[i] == arr2[j]) {
ans.add(arr1[i]);
i++;
j++;
}
else {
j++;
}

return list.stream().toArray(int[]::new);
}

Подчистил немного. Добавлены некоторые проверки / Джава 8 / неиспользованный " к " переменной

0
ответ дан 5 февраля 2018 в 07:02 Источник Поделиться