降低查找数组元素绝对和的复杂度 [英] Reducing complexity to find the absolute sum of an array elements

问题描述

我在 Hackerrank 上遇到了这个问题.https://www.hackerrank.com/challenges/playing-with-numbers/问题

I got this problem on Hackerrank. https://www.hackerrank.com/challenges/playing-with-numbers/problem

给定一个整数数组，您必须回答许多查询.每个查询由一个整数 x 组成，并按如下方式执行:

Given an array of integers, you must answer a number of queries. Each query consists of a single integer, x and is performed as follows:

• 将 x 添加到数组的每个元素中，为以后的任何查询永久修改它.
• 找出数组中每个元素的绝对值，并在新行打印绝对值的总和.

我只需要完成下面的方法，

All I need to complete the following method,

static int[] solution(int[] arr, int[] queries)

这里，arr 是包含 n 个元素的数组和 queries 包含我需要与数组 arr 的每个值相加的所有 x，然后获取 arr 元素的绝对和代码> arr.所以结果数组将与数组queries 的大小相同，假设大小为m.该方法将返回一个 m 元素的数组.

Here, arr is the array with n elements and queries contain all the x that I need to add with each value of the array arr and then get the absolute sum of the elements of arr. So the resultant array will be the same size as array queries, say that size is m. The method will return an array of m elements.

以下是我的实现.

       static int[] solution(int[] arr, int[] queries)
       {

          int[] result = new int[queries.length];

          for (int i = 0; i < queries.length; i++)
          {
             int total = 0;

             for (int j = 0; j < arr.length; j++)
             {
                arr[j] += queries[i];

                if (arr[j] > 0)
                   total += arr[j];
                else
                   total -= arr[j];
             }
             result[i] = total;
          }

          return result;
       }

它工作正常，它的复杂度是 O(mn)，但我需要用 O(nlog_m) 或 O(mlog_n) 或接近那个.

It works fine, its complexity is O(mn), but I need to do it with a complexity of something O(nlog_m) or O(mlog_n) or close to that.

推荐答案

Inspired 在以下链接中由 h4z3 给出的解释，绝对元素总和

Inspired by the explanation given by h4z3 in the following link, Absolute Elements Sums

我已经用 Java 实现了这个想法，

I've implemented the idea in Java,

复杂度为 O(n log n).

   static int bisect_left(int[] num, int x)
   {
      int low = 0;
      int high = num.length - 1;

      while (low < high)
      {
         int mid = (low + high) / 2;

         if (num[mid] >= x)
            high = mid - 1;
         else
            low = mid + 1;
      }

      return (num[low] < x) ? low + 1 : low;
   }

   static int[] solution(int[] arr, int[] queries)
   {
      Arrays.sort(arr); // O(n log n)

      int N = arr.length;

      int[] results = new int[queries.length];
      int[] sc = new int[N + 1];
      sc[0] = 0;
      sc[1] = arr[0];

      for (int i = 1; i < N; i++)
         sc[i + 1] = sc[i] + arr[i];

      int q = 0;
      for (int i = 0; i < queries.length; i++)  //  O(m)
      {
         q += queries[i];

         int n = bisect_left(arr, -q);  //  O(log n)

         results[i] = sc[N] + q * N - 2 * (sc[n] + q * n);
      }

      return results;
   }

这篇关于降低查找数组元素绝对和的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！