logo标签列表

高效算法下选择两个数字的方法数

c++algorithm
3

我解决了这个问题，但是在在线评测中却得到了TLE（时间限制超出）。

程序的输出是正确的，但我认为可以改进方式使其更加高效！

问题：

给定 n 个整数，计算我们可以选择两个元素的方法数，使它们的绝对差小于 32。

更正式地说，计算成对的数量 (i, j) (1 ≤ i < j ≤ n)，使得

|V[i] - V[j]| < 32。其中，|X| 表示 X 的绝对值。

输入：

输入的第一行包含一个整数 T，表示测试用例的数量 (1 ≤ T ≤ 128)。

每个测试用例以一个整数 n (1 ≤ n ≤ 10,000) 开始。

下一行包含 n 个整数 (1 ≤ V[i] ≤ 10,000)。

输出：

对于每个测试用例，输出成对数的数量。

C++代码：

int main() {
    int T,n,i,j,k,count;
    int a[10000];
    cin>>T;

for(k=0;k<T;k++)
 {   count=0;
     cin>>n;
    for(i=0;i<n;i++)
    {
      cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
        for(j=i;j<n;j++)
        {
          if(i!=j)
          {
            if(abs(a[i]-a[j])<32)
                count++;
          }
        }
    }
    cout<<count<<endl;
 }
    return 0;
}

我需要帮助，如何使用更高效的算法来解决这个问题？

我认为对输入进行排序将会有所帮助。这样你就不必每次都执行O(n^2)了。 - Haris
10个回答
6

尽管我之前的回答有些愚蠢，但实际上根本不需要对数据进行排序。相反，您应该计算数字的频率。

然后，您只需要在遍历可能的值时跟踪可配对数字的数量即可。很抱歉没有C ++示例，但Java应该也能读懂：

int solve (int[] numbers) {                                                 
    int[] frequencies = new int[10001];                                     
    for (int i : numbers) frequencies[i]++;                                 
    int solution = 0;                                                       
    int inRange = 0;                                                        
    for (int i = 0; i < frequencies.length; i++) {                          
        if (i > 32) inRange -= frequencies[i - 32];                         
        solution += frequencies[i] * inRange;                               
        solution += frequencies[i] * (frequencies[i] - 1) / 2;              
        inRange += frequencies[i];                                           
    }                                                                        
    return solution;                                                         
}
你的想法是对的，频率数组是最好的方式，但你的代码输出不正确。 - Oghli
你认为我的代码在哪个输入上失败了？因为我测试过的所有内容 - 包括你链接中提供的示例 - 都似乎给出了正确的结果。 - Stef
抱歉，Stef，我错了，你的解决方案完美地解决了问题。你能否详细解释一下你的算法，以便每个人都可以参考？ - Oghli
你能解释一下从这个循环的代码行到结尾 for (int i = 0; i < frequencies.length; i++) 的意思吗？ - Oghli
3
#include <bits/stdc++.h> 
using namespace std;

int a[10010];
int N;
int search (int x){
int low = 0;
int high = N;
while (low < high)
{
    int mid = (low+high)/2;
    if (a[mid] >= x) high = mid;
    else low = mid+1;
}
return low;
}

int main() {
    cin >> N;
    for (int i=0 ; i<N ; i++) cin >> a[i];
    sort(a,a+N);
    long long ans = 0;
    for (int i=0 ; i<N ; i++)
    {
        int t = search(a[i]+32);
        ans += (t -i - 1);
    }

    cout << ans << endl;
    return 0;
}
2
您可以对数字进行排序，然后使用滑动窗口。从最小的数字开始，只要它们不大于最小数字+31，就使用std::deque填充数字。然后在外部循环中，对于每个数字，更新滑动窗口并将滑动窗口的新大小添加到计数器中。可以在内部循环中执行滑动窗口的更新，首先pop_front每个小于外部循环当前数字的数字，然后push_back每个不大于外部循环当前数字+31的数字。
你也可以用频率数组或二分查找来解决这个问题。 - Oghli
1
一种更快的解决方案是先对数组进行排序，然后遍历排序后的数组，对于每个元素只访问其右侧的元素，直到差值超过31。
排序可能可以通过计数排序完成（因为1≤V[i]≤10,000）。因此，您可以在排序部分获得线性时间。但这可能不是必要的（也许快速排序足以获取所有点）。
此外，您可以针对内部循环（“当前元素向右走”部分）进行技巧处理。请记住，如果S[i+k]-S[i]<32，则S[i+k]-S[i+1]<32，其中S是V的排序版本。使用此技巧，整个算法变成了线性。
1
这可以通过对数据进行恒定次数的遍历来完成，实际上可以在不受“间隔”值（在您的情况下为32）影响的情况下完成。这是通过填充一个数组来完成的，其中a[i] = a[i-1] + number_of_times_i_appears_in_the_data - 简单地说，a[i] 包含小于等于i的元素总数。

代码（针对单个测试用例）：

static int UPPER_LIMIT = 10001;
static int K = 32;
int frequencies[UPPER_LIMIT] = {0}; // O(U)
int n;
std::cin >> n;
for (int i = 0; i < n; i++) { // O(n)
 int x;
 std::cin >> x;
 frequencies[x] += 1;
}
for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
    frequencies[i] += frequencies[i-1];
}
int count = 0;
for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
  int low_idx = std::max(i-32, 0);
  int number_of_elements_with_value_i = frequencies[i] - frequencies[i-1];
  if (number_of_elements_with_value_i == 0) continue;
  int number_of_elements_with_value_K_close_to_i =
      (frequencies[i-1] - frequencies[low_idx]);
  std::cout << "i: " << i << " number_of_elements_with_value_i: " << number_of_elements_with_value_i << " number_of_elements_with_value_K_close_to_i: " << number_of_elements_with_value_K_close_to_i << std::endl;
  count += number_of_elements_with_value_i * number_of_elements_with_value_K_close_to_i;
  // Finally, add "duplicates" of i, this is basically sum of arithmetic 
  // progression with d=1, a0=0, n=number_of_elements_with_value_i
  count += number_of_elements_with_value_i * (number_of_elements_with_value_i-1) /2;
}
std::cout << count;

在IDEone上有一个完整的编程示例。

1
这个解决方案可以被认为是O(N)来处理N个输入数字，并且在处理输入时具有恒定的时间：
#include <iostream>
using namespace std;

void solve()
{
    int a[10001] = {0}, N, n, X32 = 0, ret = 0;
    cin >> N;
    for (int i=0; i<N; ++i)
    {
        cin >> n;
        a[n]++;
    }

    for (int i=0; i<10001; ++i)
    {
        if (i >= 32)
            X32 -= a[i-32];
        if (a[i])
        {
            ret += a[i] * X32;
            ret += a[i] * (a[i]-1)/2;
            X32 += a[i];
        }
    }
    cout << ret << endl;
}

int main()
{
    int T;
    cin >> T;
    for (int i=0 ; i<T ; i++)
        solve();
}

在ideone上运行此代码

解决方案说明：a[i]表示输入序列中i出现的次数。 然后遍历整个数组，X32跟踪在i范围内的元素数量。唯一棘手的部分实际上是正确计算某个i多次重复时的情况：a[i] * (a[i]-1)/2。就这些。

@MohammadOghli 这个解决方案返回了预期的结果吗？ - Pavel P
1
这怎么是O(1)的？它有一个从0到N-1的循环。 - Ap31
1
我认为你是对的，处理N个输入数字的时间复杂度是O(N)。我已经更新了答案。我不认为反向循环会以任何方式影响复杂度。 - Pavel P
1
您可以对范围进行排序，然后使用break来结束循环，每当范围超出时。
int main()
{
    int t;
    cin>>t;

    while(t--){
        int n,c=0;
        cin>>n;

        int ar[n];
        for(int i=0;i<n;i++)
            cin>>ar[i];

        sort(ar,ar+n);

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(ar[j]-ar[i] < 32)
                    c++;
                else
                    break;
            }
        }
        cout<<c<<endl;
    }
}

或者，您可以使用哈希数组来表示范围并标记每个元素的出现情况，然后循环遍历并检查每个元素，即是否存在x = 32 - y。

谢谢回答，但是由于它的复杂度为O(n^2)，所以返回了超时限制。 - Oghli
1
一个好的方法是将数字分成不同的桶：
constexpr int limit = 10000;
constexpr int diff = 32;
constexpr int bucket_num = (limit/diff)+1;
std::array<std::vector<int>,bucket_num> buckets;

cin>>n;
int number;
for(i=0;i<n;i++)
{
    cin >> number;
    buckets[number/diff].push_back(number%diff);
}

显然，处于同一个桶中的数字彼此之间足够接近以满足要求，因此我们只需计算所有配对即可：
int result = std::accumulate(buckets.begin(), buckets.end(), 0,
                  [](int s, vector<int>& v){ return s + (v.size()*(v.size()-1))/2; });

那些不在相邻桶中的数字无法组成任何可接受的对，因此我们可以忽略它们。
这留下了最后一个特例 - 相邻的桶 - 可以通过多种方式解决：
for(int i=0;i<bucket_num-1;i++)
   if(buckets[i].size() && buckets[i+1].size())
      result += adjacent_buckets(buckets[i], buckets[i+1]);

就我个人而言，我比较喜欢使用“发生频率”这种单桶量表的方法，但也可能存在更好的选择：

int adjacent_buckets(const vector<int>& bucket1, const vector<int>& bucket2)
{
    std::array<int,diff> pairs{};
    for(int number : bucket1)
     {
         for(int i=0;i<number;i++)
            pairs[i]++;
     }

    return std::accumulate(bucket2.begin(), bucket2.end(), 0,
                           [&pairs](int s, int n){ return s + pairs[n]; }); 
}

此函数首先构建一个“与 i 足够接近的较低桶中的数字”的数组，然后将该数组中对应于较高桶数字的值相加。通常情况下，这种方法的复杂度为O（N），在最好的情况下，它只需要进行一次遍历，并且总体上应该足够快。工作示例
感谢您的努力，同时提供了一个时间复杂度为O(n)的好解决方案。 - Oghli
0
你应该从排序输入开始。
然后，如果你的内部循环检测到距离增长超过32，你可以从中断它。
1
如果有许多相等的数字，那仍然会很慢，时间复杂度仍为O(N^2)。 - Serge Rogatch
0

感谢大家的努力和时间来解决这个问题。

我很感激所有尝试解决它的人。

在在线评测中测试答案后，我发现正确且最有效的解决方案算法是Stef's Answer和AbdullahAhmedAbdelmonem's answer，同时pavel的解决方案也是正确的，但它与Stef的解决方案在不同的语言C++中完全相同。

Stef的代码在codeforces在线评测中执行时间为358毫秒，并被接受。

同时，AbdullahAhmedAbdelmonem的代码在codeforces在线评测中执行时间为421毫秒，并被接受。

如果他们对他们的算法进行详细的解释，赏金将授予其中之一。

您可以尝试您的解决方案，并在选择问题E. Time Limit Exceeded?后将其提交到codeforces在线评测网站上。

此外，我还发现了一个使用频率数组更易理解的优秀算法解决方案，其复杂度为O(n)。

在这个算法中，您只需要为插入到数组中的每个元素选择特定的范围，即：
begin = element - 32  
end = element + 32

然后对于频率数组中插入的每个元素，在该范围内计算成对数目：

int main() {
    int T,n,i,j,k,b,e,count;
    int v[10000];
    int freq[10001];

    cin>>T;   
 for(k=0;k<T;k++)
 { 
    count=0;
    cin>>n;
    for(i=1;i<=10000;i++)
    {
      freq[i]=0;
    }
    for(i=0;i<n;i++)
    {
     cin>>v[i];
    }   
    for(i=0;i<n;i++)
    {
     count=count+freq[v[i]];

     b=v[i]-31;
     e=v[i]+31;

     if(b<=0)
         b=1;
     if(e>10000)
        e=10000;

     for(j=b;j<=e;j++)
      {
        freq[j]++;
      }
    }
    cout<<count<<endl;
 }
    return 0;
}

最后我认为解决这种问题的最佳方法是使用频率数组并计算特定范围内的成对数量，因为其时间复杂度为O（n）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接