c – 阵列中3个长度AP的最快算法计数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c – 阵列中3个长度AP的最快算法计数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2524字，纯文字阅读大概需要4分钟。

内容图文

我想解决this CodeChef挑战：

假设我们得到一个N(范围100,000)元素的数组A.我们要找到3个这样的元素1< = Ai,Aj,Ak< = 30,000的所有对的计数,这样  Aj-Ai = Ak-Aj,i <i. j<="" ?<br=""> 
换句话说,Ai,Aj,Ak处于算术级数.例如对于Array：

9 4 2 3 6 10 3 3 10

所以AP是：

{2,6,10},{9,6,3},{9,6,3},{3,3,3},{2,6,10} 

所以答案是5.

 我的方法

我尝试的是采用过去和过去命名的30,000个长阵列.最初右侧包含每个1-30,000元素的计数.
如果我们在第i个位置经过存储,则在i之前存储数组值的数量,并且在i之后存储数组的数量.我只是循环查找数组中所有可能的常见差异.这是代码：

right[arr[1]]--;

for(i=2;i<=n-1;i++)
{
    past[arr[i-1]]++;
    right[arr[i]]--;
    k=30000 - arr[i];
    if(arr[i] <= 15000)
        k=arr[i];
    for(d=1;d<=k;d++)
    {
        ans+= right[arr[i] + d]*past[arr[i]-d] + past[arr[i] + d]*right[arr[i]-d];
    }
    ans+=past[arr[i]]*right[arr[i]];
}

但这让我的时间限制超过了.请帮助更好的算法.

解决方法:

如果您首先通过列表并且仅提取可能具有3个术语AP的数字对(差异为0 mod 2),则可以大大缩短执行时间.然后在这些对之间进行迭代.

伪C -y代码：

// Contains information about each beginning point
struct BeginNode {
  int value;
  size_t offset;
  SortedList<EndNode> ends;  //sorted by EndNode.value
};

// Contains information about each class of end point
struct EndNode {
  int value;
  List<size_t> offsets; // will be sorted without effort due to how we collect offsets
};

struct Result {
  size_t begin;
  size_t middle;
  size_t end;
};

SortedList<BeginNode> nodeList;
foreach (auto i : baseList) {
  BeginNode begin;
  node.value = i;
  node.offset = i's offset; //you'll need to use old school for (i=0;etc;i++) with this
  // baseList is the list between begin and end-2 (inclusive)
  foreach (auto j : restList) { 
    // restList is the list between iterator i+2 and end (inclusive)
    // we do not need to consider i+1, because not enough space for AP
    if ((i-j)%2 == 0) { //if it's possible to have a 3 term AP between these two nodes
      size_t listOffset = binarySearch(begin.ends);
      if (listOffset is valid) {
        begin.ends[listOffset].offsets.push_back(offsets);
      } else {
        EndNode end;
        end.value = j;
        end.offsets.push_back(j's offset);
        begin.ends.sorted_insert(end);
      }
    }
  }
  if (begin has shit in it) {
    nodeList.sorted_insert(begin);
  }
}
// Collection done, now iterate over collection

List<Result> res;
foreach (auto node : nodeList) {
  foreach (auto endNode : node.ends) {
    foreach (value : sublist from node.offset until endNode.offsets.last()) {
      if (value == average(node.value, endNode.value)) {
        // binary_search here to determine how many offsets in "endNode.offsets" "value's offset" is less than.
        do this that many times:
          res.push_back({node.value, value, endNode.value});
      }
    }
  }
}

return res;

内容总结

以上是互联网集市为您收集整理的c – 阵列中3个长度AP的最快算法计数全部内容，希望文章能够帮你解决c – 阵列中3个长度AP的最快算法计数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---