在列表中分组数字

Question

我遇到了以下问题，

您将获得一个包含 n 个元素的数组 A。这些元素现在被添加到一个新的列表L中，该列表最初是空的，根据给定的q查询以一定的顺序排列。

• 在每个查询中，都会为您提供一个与数组A中的A[i]对应的整数i。这意味着您必须将元素A[i】添加到列表L中。
• 将每个元素添加到列表L后，对列表L中的元素进行分组。如果数组A中的索引是连续的，则两个元素将属于同一组
• 对于每个组，我们将组的值定义为axb，其中a是该组中最大的值，b是该组的大小

打印每个元素添加到列表L后形成的所有组中的最大组值。

我的方法是使用map

int g[a.size()+2];       //+2 because queries start with index 1, and g[i] corresponds to a[i-1] 
for(int i=0;i<a.size()+2;i++)
    g[i]=-1;
int gno=1;
map<int,vector<int> > m;
vector<int> ans;
int mx=0;
for(unsigned int i=0;i<queries.size();i++){
    int q = queries[i];
    if(g[q-1]==-1 && g[q+1]==-1){
      //create new group with current eleent as first element
        g[q] = gno;        //gno is the group number.
        vector<int> v;

        v.push_back(1);
        v.push_back(a[q-1]);
        m[gno]=v;
        mx = max(mx,m[gno][0]*m[gno][1]);
        gno++;
    }
    else if(g[q-1]!=-1 && g[q+1]==-1){
      //join current element to left group
        g[q] = g[q-1];
        m[g[q]][0]++;
        m[g[q]][1] = max(m[g[q]][1],a[q-1]);
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    else if(g[q-1]==-1 && g[q+1]!=-1){
      //join current element to right group
        g[q] = g[q+1];
        m[g[q]][0]++;
        m[g[q]][1] = max(m[g[q]][1],a[q-1]);
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    else{
       //join both groups to left and right
        g[q]=g[q-1];
        int g1 = g[q];
        int i;
        m[g[q]][0] += 1 + m[g[q+1]][0];
        m[g[q]][1] = max(m[g[q]][1],max(a[q-1],m[g[q+1]][1]));
        for(i=q+1;g[i]==g[i+1];i++){
            g[i]=g1;
        }
        g[i]=g1;
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    ans.push_back(mx);
}

.




Answer 1

匿名用户

让我们从两个简化的假设开始：

• 没有重复项。一旦给定的索引 i 被“查询”，它就永远不会再被查询了。
• 无负数。所有元素都是正数或零值，因此组中的最大值始终为正数或零，因此展开一个组（或合并两个组）永远不会导致整体“最大组值”降低。

（下面我将进一步说明如何不需要这些假设，但目前这将简化情况。）

因此，每当我们“查询”索引i时，有四种情况：

• i-1当前是一个组的右endpoint（我指的是它的最大索引），i 1当前是另一个组的左endpoint。
  • 在这种情况下，我们需要将两组合并为一个组，i弥合它们之间的差距。
  • 在这种情况下，我们需要扩展组以涵盖i。
  • 在这种情况下，与前一个案例一样，我们需要扩展组以覆盖 i。
  • 在这种情况下，我们有一个只有一个元素的新组。

  在所有情况下，需要注意的关键是，我们只对组的endpoint感兴趣。因此，我们不需要从索引到其组的一般映射。 。 。这很好，因为当我们合并两个组时，然后去更新一个组中的每个索引以指向另一个组将是昂贵的。

  所以我们只需要三个映射：

  std::unordered_map<int, int> map_from_left_endpoint_to_right_endpoint;
  std::unordered_map<int, int> map_from_right_endpoint_to_left_endpoint;
  std::unordered_map<int, int> map_from_left_endpoint_to_largest_value;
  

  为了区分这四种情况，我们使用< code > map _ from _ right _ endpoint _ to _ left _ endpoint . find(I-1)(它返回一个迭代器，指向< code>i-1是其右endpoint的组的左endpoint，如果适用的话；否则，它返回< code > map _ from _ right _ endpoint _ to _ left _ endpoint . end()。然后，当条目变得不再适用时(由于组在给定的方向上被扩展或合并),除了(显然)插入新的条目，并更新现有条目的值之外，我们删除条目。

  除了这些值，我们还需要一个

  int maximum_group_value = 0;
  

  每当我们扩展一个组或合并两个组时，我们都会检查结果组的值（即其largestvalue*（rightendpoint-lefftendpoint1）是否大于maximumgroupvalue。如果是，我们更新maximum_group_value并返回它；如果不是，则按原样返回maximumgroupvalue。

  现在，如果允许重复，那么给定的索引< code>i可能在它已经属于一个组之后被“查询”呢？

  最简单的方法是简单地跟踪已经被查询的< code > I ；但是，如果需要，更好的方法可能是将< code > map _ from _ left _ endpoint _ to _ right _ endpoint 从< code>std::unordered_map更改为< code>std::map，然后像这样使用:

  bool is_already_in_a_group(
      std::map<int, int> const & map_from_left_endpoint_to_right_endpoint,
      int const i) {
    // get iterator to first element *after* index (or to 'end()' if no such):
    auto iter = map_from_left_endpoint_to_right_endpoint.upper_bound(index);
    // if that pointer points to 'begin()', then there are no elements
    // at or before index:
    if (iter == map_from_left_endpoint_to_right_endpoint.begin()) {
      return false;
    }
    // otherwise, move iterator to point to the last element whose key is
    // less than or equal to index:
    --iter;
    // . . . and check whether the value of that element is greater than
    // or equal to index (meaning that [key, value] spans index):
    return iter->second >= index;
  }
  

  检查mapfromleft_endpoint_to_right_endpoint中小于或等于i的最大键是否映射到大于或等于i的值。

  这为我们上面的案例分析增加了第五种情况——“如果i已经在一个组中，什么也不做并返回maximum_group_value”——但除此之外，没有任何效果。

  请注意，如果我们愿意，同样的方法还可以让我们消除map_from_right_endpoint_to_left_endpoint：通过将返回语句更改为返回 iter，可以轻松地将上述函数调整为 int get_left_endpoint_for_right_endpoint

  此时，定义一个包含三个字段（left_endpoint、right_endpoint和largest_value）的Group类是明智的，并且只保留一个map_from_left_endpoint_to_group。

  最后——如果允许负值，使得“最大组值”实际上可以作为查询的结果而减少怎么办？（例如，如果数组元素是[-1，-10]并且查询是i=0，i=1，那么结果是maximum_group_value=-1，maximum_group_value=-2。）在这种情况下，我们需要跟踪所有当前组的值，因为它们中的任何一个都可能突然变成最大值。

  为此，我们可以维护一堆按值排序的组，而不是存储单个int maximum_group_value，每次创建/扩展/合并组时都会将其推送到其中。（我们可以只使用标准：：向量

  作为优化，我们还可以存储intmaximum_group_value，并在遇到非负数组元素后消除堆（因为一旦给定组包含非负数组元素，其值就不会再减少，显然最大组值将是其中一个组的值）。

Answer 2

实际上，我不会构建list L。寻找如何处理新值的时间成本可能太高:它本身是一个新组吗？它扩展了现有的组吗？两个组需要合并成一个组吗？如果第一个值相距很远，您将有许多组，并且您需要用每个新的传入值迭代它们:这是没有效率的。

我会先收集所有值，然后才看看它们如何适合组。

有两种收集值的方法:

>

将它们存储在列表中，并在收集完所有值后，按升序对列表进行排序

标记大小为 n 的布尔值数组中的条目。这样，您就不必对其进行排序，但之后您确实需要迭代整个数组以按升序查找值。

当 q 远小于 n 时，方法 1 将是最好的。方法 2 对于更大的 q 会更好。

使用这两种方法，您将能够按升序迭代找到的值，同时您可以识别组、它们的值，并跟踪最大的组值。只需要一次扫描即可找到答案。