找出阵列中(i,j)对的总数,以使i <j且a [i] + a [j] = i + j. [英] Find total number of (i,j) pairs in an array such that i<j and a[i]+a[j]=i+j.
问题描述
我有一个使用两个循环的幼稚解决方案,但我想将时间复杂度提高为O(nlogn).有更好的方法吗?
I have a naive solution which uses two loops, but I want to improve the time complexity as O(nlogn). Any better approach available?
该数组未排序,并且也可以具有负值.
The array is unsorted and can have negative values too.
样本测试用例: 数组:1 0 3 2
Sample Test Case: Array: 1 0 3 2
输出: 4
说明: 索引-(0,1),(0,3),(1,2),(2,3)是满足给定约束的对.
Explanation: Indices - (0,1), (0,3), (1,2), (2,3) are the pairs which satisfy the given constraints.
推荐答案
问题:find (i,j), i<j, s.t. a[i] + a[j] = i + j
我提出以下方法:
-
设置
b[i] = a[i] - i
问题变为:find (i,j), i<j, s.t. b[i] + b[j] = 0
复杂度:O(n)
Set
b[i] = a[i] - i
The problem becomes:find (i,j), i<j, s.t. b[i] + b[j] = 0
Complexity: O(n)
在std :: vector(或std :: array)中创建对象c[i] = (b[i],i)
(例如,结构)
复杂度:O(n)
Create objects c[i] = (b[i],i)
, a struct for example, in a std::vector (or std::array)
Complexity: O(n)
根据b
值对c[i]
对进行排序->获得d[j] = (v[j], i[j])
,对数组进行排序
复杂度:O(nlogn)
Sort the c[i]
pairs according to b
values -> get d[j] = (v[j], i[j])
, sorted array
Complexity: O(nlogn)
查找所有对j,k
,使v[j] = -v[k]
复杂性:要排序的数组应为O(n)
Find all pairs j,k
such that v[j] = -v[k]
Complexity: the array being sorted, should be O(n)
保持案例i[j] < i[k]
复杂度:O(n)
keep the cases i[j] < i[k]
Complexity: O(n)
这篇关于找出阵列中(i,j)对的总数,以使i <j且a [i] + a [j] = i + j.的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!