3

输入：

  • 正数自然数的排序数组，

预期的复杂性：

  • 时间：O(n)
  • 额外空间：O(1)

例子：

输入：

arr = {2,3,17,30} x=10

预期行为：

该函数打印索引：1,2 并返回 true，因为 (3+17)/2 = x = 10

输入：

x = 30

预期行为：

该函数将打印索引 3 并返回 true，因为(30)/1= x = 30`

我的算法方法：

我们将从数组中的第一个元素开始取算术平均值。如果 x 大于我们的结果，我们会将数组中的下一个元素添加到算术平均值中。否则，我们将从算术平均值中减去第一个元素。

我试过了，但没有用。谁能帮我？

4

2 回答 2

1
  1. 找到最大的 k，其中 a0+a1+a2+...+ak <= k*target 的总和
  2. 如果 sum == k*target - 好的
  3. 如果 sum != k*target - 添加下一个元素，然后减去第一个元素，直到平均值变得小于或等于目标。

如果您的 k 达到数组长度，则没有解决方案。否则你有解决方案。复杂度 O(n) 就好像第 3 步您只添加一个数字，因为先前的 sum + ak+1 大于 k*target 并且您只能将左边界移动 n 次。

1. proc(array, x):
2.     sum = 0;
3.     left = 0;
4.     right = 0;
5.     do:
6.         sum += array[right];
7.         right++;
8.     while (sum+array[right] <= (right+1)*target && right<array.size);
9.     if (sum == right*target):
10.        for (i = left; i < right; i++):
11.            print(array[i] + <sep>);
12.        end_for
13.        return;
14.    end_if
15.    while (left <= right):
16.        if (right<array.size): sum += array[right++];
17.        do:
18.            sum-=array[left++]
19.        while (sum > target*(right-left));
20.        if (sum == target*(right-left)):
21.            for (i = left; i < right; i++):
22.                print(array[i] + <sep>);
23.            end_for
24.            return;
25.        end_if
26.    end_while
27.end_proc

适用于所有数字为正的数组。负数需要进行小的修改，但在采访中，他们经常询问所有数字均为正数的数组。如果没有适当的解决方案，可能需要一些额外的逃生条件。

于 2016-08-24T14:53:03.563 回答
0

如果我们计算k元素的平均值from 0 to k，我们可以知道平均值from 1 to k或关于from 0 to k + 1？两个平均值1 to k都0 to k + 1等于或大于第一元素的平均值k。为什么？从子集from 0 to k到子集from 1 to k，意味着删除最少的元素，因此可能不会降低总平均值。从子集from 0 to k到子集from 0 to k + 1，意味着添加一个不小于其他元素的元素，因此它可能不会降低总平均值。

我们是否知道给定数组中的哪个数字必须是结果的一部分？是的，这是最后一个小于或等于目标的。为什么？当它相等时，我们就完成了当它不相等时，我们需要同时拥有更大和更低的元素。

然后，我们通过从右侧添加元素并从左侧减少来保持平均值。

public static int[] findMean(int[] input, int target) {
    int firstGreater = 0;
    int n = input.length;
    while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
    if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
    int left = firstGreater - 1, right = firstGreater;
    long sum = input[left];
    while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
        if((right - left) * target > sum) sum += input[right++];
        else sum += input[--left];
    }
    if((right - left) * target != sum) {
        left = right = -1;
    }
    return new int[]{left, right - 1};
}
于 2016-08-24T22:28:05.827 回答