Учитывая массив чисел, возвращаем массив продуктов всех других чисел (без деления)

Меня задали этот вопрос на собеседовании, и я хотел бы знать, как другие решат его. Мне больше всего нравится Java, но приветствуются решения на других языках.

Учитывая массив чисел nums , возвращаем массив products чисел, где products[i] являются произведением всех nums[j], j != i

 Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] 

Вы должны сделать это в O(N) без использования деления.

Объяснение метода полигеновых смазочных материалов заключается в том, чтобы сконструировать массивы (в случае для 4 элементов)

 { 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], } { a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, } 

Оба они могут выполняться в O (n), начиная с левого и правого краев соответственно.

Затем умножение двух элементов массива на элемент дает требуемый результат

Мой код будет выглядеть примерно так:

 int a[N] // This is the input int products_below[N]; p=1; for(int i=0;i=0;--i) { products_above[i]=p; p*=a[i]; } int products[N]; // This is the result for(int i=0;i 

Если вам нужно быть O (1) в пространстве, вы тоже можете это сделать (что менее понятно IMHO)

 int a[N] // This is the input int products[N]; // Get the products below the current index p=1; for(int i=0;i=0;--i) { products[i]*=p; p*=a[i]; } 

Ниже приведена небольшая рекурсивная функция (в C ++) для выполнения модификации. Это требует O (n) дополнительного пространства (в стеке). Предполагая, что массив находится в a, а N содержит длину массива, мы имеем

 int multiply(int *a, int fwdProduct, int indx) { int revProduct = 1; if (indx < N) { revProduct = multiply(a, fwdProduct*a[indx], indx+1); int cur = a[indx]; a[indx] = fwdProduct * revProduct; revProduct *= cur; } return revProduct; } 

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

 import java.util.Arrays; public class Products { static int[] products(int... nums) { final int N = nums.length; int[] prods = new int[N]; Arrays.fill(prods, 1); for (int i = 0, pi = 1 , j = N-1, pj = 1 ; (i < N) && (j >= 0) ; pi *= nums[i++] , pj *= nums[j--] ) { prods[i] *= pi ; prods[j] *= pj ; } return prods; } public static void main(String[] args) { System.out.println( Arrays.toString(products(1, 2, 3, 4, 5)) ); // prints "[120, 60, 40, 30, 24]" } } 

Инварианты цикла – это pi = nums[0] * nums[1] *.. nums[i-1] и pj = nums[N-1] * nums[N-2] *.. nums[j+1] . Часть i слева – это логика «префикс», а часть j справа – логика «суффикса».


Рекурсивный однострочный

Ясмит дал (красивое!) Рекурсивное решение; Я превратил его в этот (отвратительный!) Java-вкладыш. Он выполняет модификацию на месте , с O(N) временным пространством в стеке.

 static int multiply(int[] nums, int p, int n) { return (n == nums.length) ? 1 : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1)) + 0*(nums[n] *= p); } int[] arr = {1,2,3,4,5}; multiply(arr, 1, 0); System.out.println(Arrays.toString(arr)); // prints "[120, 60, 40, 30, 24]" 

Перевод решения Майкла Андерсона в Haskell:

 otherProducts xs = zipWith (*) below above where below = scanl (*) 1 $ init xs above = tail $ scanr (*) 1 xs 

Тщательно обходя правило «без дивизий»:

 sum = 0.0 for i in range(a): sum += log(a[i]) for i in range(a): output[i] = exp(sum - log(a[i])) 

Здесь вы идете, простое и чистое решение с сложностью O (N):

 int[] a = {1,2,3,4,5}; int[] r = new int[a.length]; int x = 1; r[0] = 1; for (int i=1;i0;i--){ x=x*a[i]; r[i-1]=x*r[i-1]; } for (int i=0;i 

C ++, O (n):

 long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies()); transform(in.begin(), in.end(), back_inserter(res), bind1st(divides(), prod)); 
  1. Путешествие влево-> Вправо и сохраните продукт. Назовите это Прошлое. -> O (n)
  2. Поездка вправо -> влево сохраните продукт. Назовите это будущее. -> O (n)
  3. Результат [i] = Прошлое [i-1] * future [i + 1] -> O (n)
  4. Прошлое [-1] = 1; и Future [n + 1] = 1;

На)

Вот мое решение в современном C ++. Он использует std::transform и довольно легко запоминается.

Онлайн-код (wandbox).

 #include #include #include using namespace std; vector& multiply_up(vector& v){ v.insert(v.begin(),1); transform(v.begin()+1, v.end() ,v.begin() ,v.begin()+1 ,[](auto const& a, auto const& b) { return b*a; } ); v.pop_back(); return v; } int main() { vector v = {1,2,3,4,5}; auto vr = v; reverse(vr.begin(),vr.end()); multiply_up(v); multiply_up(vr); reverse(vr.begin(),vr.end()); transform(v.begin(),v.end() ,vr.begin() ,v.begin() ,[](auto const& a, auto const& b) { return b*a; } ); for(auto& i: v) cout << i << " "; } , #include #include #include using namespace std; vector& multiply_up(vector& v){ v.insert(v.begin(),1); transform(v.begin()+1, v.end() ,v.begin() ,v.begin()+1 ,[](auto const& a, auto const& b) { return b*a; } ); v.pop_back(); return v; } int main() { vector v = {1,2,3,4,5}; auto vr = v; reverse(vr.begin(),vr.end()); multiply_up(v); multiply_up(vr); reverse(vr.begin(),vr.end()); transform(v.begin(),v.end() ,vr.begin() ,v.begin() ,[](auto const& a, auto const& b) { return b*a; } ); for(auto& i: v) cout << i << " "; } 

Это O (n ^ 2), но f # выглядит настолько красиво:

 List.fold (fun seed i -> List.mapi (fun jx -> if i=j+1 then x else x*i) seed) [1;1;1;1;1] [1..5] 

Tricky:

Используйте следующее:

 public int[] calc(int[] params) { int[] left = new int[n-1] in[] right = new int[n-1] int fac1 = 1; int fac2 = 1; for( int i=0; i 

Да, я уверен, что я пропустил некоторые i-1 вместо i, но это способ его решения.

Также существует неоптимальное решение O (N ^ (3/2)). Это довольно интересно.

Первая предварительная обработка каждого частичного умножения размера N ^ 0,5 (это выполняется по сложности времени O (N)). Затем вычисление для каждого другого значения-множественного числа может быть выполнено в 2 * O (N ^ 0,5) времени (почему? Потому что вам нужно всего лишь несколько последних элементов других ((N ^ 0.5) – 1) чисел, и умножьте результат на ((N ^ 0.5) – 1) числа, принадлежащие к группе текущего числа). Выполняя это для каждого числа, можно получить время O (N ^ (3/2)).

Пример:

4 6 7 2 3 1 9 5 8

частичные результаты: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Чтобы вычислить значение 3, нужно умножить значения других групп 168 * 360, а затем на 2 * 1.

 public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int[] result = { 1, 1, 1, 1, 1 }; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < i; j++) { result[i] *= arr[j]; } for (int k = arr.length - 1; k > i; k--) { result[i] *= arr[k]; } } for (int i : result) { System.out.println(i); } } 

Это решение я придумал, и я нашел его настолько ясным, что вы думаете !?

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

 #include  unsigned array[5] = { 1,2,3,4,5}; int main(void) { unsigned idx; unsigned left[5] , right[5]; left[0] = 1; right[4] = 1; /* calculate products of numbers to the left of [idx] */ for (idx=1; idx < 5; idx++) { left[idx] = left[idx-1] * array[idx-1]; } /* calculate products of numbers to the right of [idx] */ for (idx=4; idx-- > 0; ) { right[idx] = right[idx+1] * array[idx+1]; } for (idx=0; idx <5 ; idx++) { printf("[%u] Product(%u*%u) = %u\n" , idx, left[idx] , right[idx] , left[idx] * right[idx] ); } return 0; } 

Результат:

 $ ./a.out [0] Product(1*120) = 120 [1] Product(1*60) = 60 [2] Product(2*20) = 40 [3] Product(6*5) = 30 [4] Product(24*1) = 24 

(ОБНОВЛЕНИЕ: теперь я смотрю ближе, это использует тот же метод, что и Майкл Андерсон, Даниэль Миговски и полигеновые смазки)

 def productify(arr, prod, i): if i < len(arr): prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1) retval = productify(arr, prod, i + 1) prod[i] *= retval return retval * arr[i] return 1 

arr = [1, 2, 3, 4, 5] prod = [] productify (arr, prod, 0) print prod

Добавление моего решения для javascript здесь, поскольку я не нашел никого, предлагающего это. Что нужно разделить, кроме как подсчитать количество раз, когда вы можете извлечь номер из другого номера? Я прошел вычисление продукта всего массива, а затем перечислил каждый элемент и вычитал текущий элемент до нуля:

 //No division operation allowed // keep substracting divisor from dividend, until dividend is zero or less than divisor function calculateProducsExceptCurrent_NoDivision(input){ var res = []; var totalProduct = 1; //calculate the total product for(var i = 0; i < input.length; i++){ totalProduct = totalProduct * input[i]; } //populate the result array by "dividing" each value for(var i = 0; i < input.length; i++){ var timesSubstracted = 0; var divisor = input[i]; var dividend = totalProduct; while(divisor <= dividend){ dividend = dividend - divisor; timesSubstracted++; } res.push(timesSubstracted); } return res; } 

Я использую C #:

  public int[] ProductExceptSelf(int[] nums) { int[] returnArray = new int[nums.Length]; List auxList = new List(); int multTotal = 0; // If no zeros are contained in the array you only have to calculate it once if(!nums.Contains(0)) { multTotal = nums.ToList().Aggregate((a, b) => a * b); for (int i = 0; i < nums.Length; i++) { returnArray[i] = multTotal / nums[i]; } } else { for (int i = 0; i < nums.Length; i++) { auxList = nums.ToList(); auxList.RemoveAt(i); if (!auxList.Contains(0)) { returnArray[i] = auxList.Aggregate((a, b) => a * b); } else { returnArray[i] = 0; } } } return returnArray; } 

Ну, это решение можно рассматривать как решение C / C ++. Допустим, у нас есть массив «a», содержащий n элементов, таких как [n], тогда псевдокод будет выглядеть следующим образом.

 for(j=0;j 

Еще одно решение: Использование деления. с двойным обходом. Умножьте все элементы, а затем начните делить его на каждый элемент.

 {-
 Рекурсивное решение с использованием подмножеств sqrt (n).  Выполняется в O (n).

 Рекурсивно вычисляет решение для sqrt (n) подмножеств размера sqrt (n). 
 Затем recursion на сумму произведения каждого подмножества.
 Тогда для каждого элемента в каждом подмножестве он вычисляет произведение с
 сумма продукта всех других продуктов.
 Затем выравнивает все подмножества.

 Повторение в течение времени выполнения T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

 Предположим, что T (n) ≤ cn в O (n).

 T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n
     ≤ sqrt (n) * c * sqrt (n) + c * sqrt (n) + n
     ≤ c * n + c * sqrt (n) + n
     ≤ (2c + 1) * n
     ∈ O (n)

 Обратите внимание, что потолок (sqrt (n)) может быть вычислен с использованием двоичного поиска 
 и O (logn), если инструкция sqrt не разрешена.
 -}

 otherProducts [] = []
 otherProducts [x] = [1]
 otherProducts [x, y] = [y, x]
 otherProducts a = foldl '(++) [] $ zipWith (\ sp -> map (* p) s) resolvedSubsets subsetOtherProducts
     где 
       n = длина a

       - Размер подмножества.  Требовать, чтобы 1 

Вот мой код:

 int multiply(int a[],int n,int nextproduct,int i) { int prevproduct=1; if(i>=n) return prevproduct; prevproduct=multiply(a,n,nextproduct*a[i],i+1); printf(" i=%d > %d\n",i,prevproduct*nextproduct); return prevproduct*a[i]; } int main() { int a[]={2,4,1,3,5}; multiply(a,5,1,0); return 0; } 

Вот немного функциональный пример, используя C #:

  Func[] backwards = new Func[input.Length]; Func[] forwards = new Func[input.Length]; for (int i = 0; i < input.Length; ++i) { var localIndex = i; backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex]; forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex]; } var output = new long[input.Length]; for (int i = 0; i < input.Length; ++i) { if (0 == i) { output[i] = forwards[i + 1](); } else if (input.Length - 1 == i) { output[i] = backwards[i - 1](); } else { output[i] = forwards[i + 1]() * backwards[i - 1](); } } 

Я не совсем уверен, что это O (n) из-за полурекурсии созданных Funcs, но мои тесты показывают, что это O (n) во времени.

Чтобы быть полным, вот код в Scala:

 val list1 = List(1, 2, 3, 4, 5) for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_)) 

Это напечатает следующее:

 120 60 40 30 24 

Программа отфильтрует текущий элемент (_! = Elem); и умножьте новый список на метод reduceLeft. Я думаю, что это будет O (n), если вы используете scala view или Iterator для ленивого eval.

// Это рекурсивное решение в Java // Вызывается как из основного продукта (a, 1,0);

 public static double product(double[] a, double fwdprod, int index){ double revprod = 1; if (index < a.length){ revprod = product2(a, fwdprod*a[index], index+1); double cur = a[index]; a[index] = fwdprod * revprod; revprod *= cur; } return revprod; } 

Оптимальное решение с O (n) временем выполнения:

  1. Для каждого элемента вычисляется произведение всех элементов, которые происходят до этого, и хранится в массиве «pre».
  2. Для каждого элемента вычислить произведение всех элементов, которые происходят после этого элемента, и сохранить его в массиве «post»,
  3. Создайте окончательный массив «результат» для элемента i,

     result[i] = pre[i-1]*post[i+1]; 
 function solution($array) { $result = []; foreach($array as $key => $value){ $copyOfOriginalArray = $array; unset($copyOfOriginalArray[$key]); $result[$key] = multiplyAllElemets($copyOfOriginalArray); } return $result; } /** * multiplies all elements of array * @param $array * @return int */ function multiplyAllElemets($array){ $result = 1; foreach($array as $element){ $result *= $element; } return $result; } $array = [1, 9, 2, 7]; print_r(solution($array)); с function solution($array) { $result = []; foreach($array as $key => $value){ $copyOfOriginalArray = $array; unset($copyOfOriginalArray[$key]); $result[$key] = multiplyAllElemets($copyOfOriginalArray); } return $result; } /** * multiplies all elements of array * @param $array * @return int */ function multiplyAllElemets($array){ $result = 1; foreach($array as $element){ $result *= $element; } return $result; } $array = [1, 9, 2, 7]; print_r(solution($array)); 

Вот еще одна простая концепция, которая решает проблему в O(N) .

  int[] arr = new int[] {1, 2, 3, 4, 5}; int[] outArray = new int[arr.length]; for(int i=0;i a * b); outArray[i] = res/arr[i]; } System.out.println(Arrays.toString(outArray)); 

Сначала мы можем исключить числа nums[j] (где j != i ) из списка, затем получить произведение остальных; Следующим является python way решить эту загадку:

 def products(nums): return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ] print products([1, 2, 3, 4, 5]) [out] [120, 60, 40, 30, 24] 

На основании ответа Билза – жаль, что я не могу комментировать, но вот версия scala, которая правильно обрабатывает дубликаты в списке и, вероятно, O (n):

 val list1 = List(1, 7, 3, 3, 4, 4) val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)} view.force 

возвращает:

 List(1008, 144, 336, 336, 252, 252) 

У меня есть решение с O(n) пространством и O(n^2) временная сложность, приведенная ниже,

 public static int[] findEachElementAsProduct1(final int[] arr) { int len = arr.length; // int[] product = new int[len]; // Arrays.fill(product, 1); int[] product = IntStream.generate(() -> 1).limit(len).toArray(); for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (i == j) { continue; } product[i] *= arr[j]; } } return product; } 
  • Как определить размер моего массива в C?
  • Быстрый способ преобразования двумерного массива в список (одномерный)
  • Исключение Java ArrayIndexOutOfBounds
  • Каков самый простой способ печати массива Java?
  • swift: изменение массивов внутри словарей
  • Сортировка массива имен папок, таких как Проводник Windows (числовые и по алфавиту) - VB.NET
  • Поиск значения max / min в массиве примитивов с использованием Java
  • equals vs Arrays.equals в Java
  • Как создать ArrayList (ArrayList ) из массива (int ) в Java
  • Почему индексы массива равны нулю на большинстве языков программирования?
  • Найти второй по величине элемент в массиве с минимальным количеством сравнений
  • Давайте будем гением компьютера.