logo标签列表

我需要一种更好的算法来解决这个问题。

c++algorithmsequences
8
以下是问题（链接：http://opc.iarcs.org.in/index.php/problems/FINDPERM）：
排列1、2、...、N的重新排列称为这些数字的排列。例如，2 4 5 1 7 6 3 8 是1、2、...、8的排列。当然，1 2 3 4 5 6 7 8 也是1、2、...、8的排列。与N的每个排列相关联的是一个名为其逆序序列的正整数序列，长度为N。这个序列的第i个元素是严格小于i且出现在i右侧的数字j的数量。对于排列2 4 5 1 7 6 3 8，逆序序列如下：0 1 0 2 2 1 2 0。第2个元素为1，因为1比2小，并且它在此排列中出现在2的右侧。类似地，第5个元素为2，因为1和3比5小但出现在此排列中5的右侧等等。另一个例子，排列8 7 6 5 4 3 2 1 的逆序序列为0 1 2 3 4 5 6 7。在这个问题中，您将获得一些排列的逆序序列。您的任务是从这个序列中重构排列。
我编写了以下代码：
#include <iostream>

using namespace std;

void insert(int key, int *array, int value , int size){
    int i = 0;
    for(i = 0; i < key; i++){
        int j = size - i;
        array[ j ] = array[ j - 1 ];
    }
    array[ size - i ] = value;
}

int main(){

    int n;
    cin >> n;
    int array[ n ];
    int key;

    for( int i = 0; i < n; i++ ){
        cin >> key;
        insert( key, array, i + 1, i);
    }

    for(int i = 0;i < n;i ++){
        cout << array[i] << " ";
    }

return 0;
}

它的工作正常，并为70%的测试用例提供正确答案，但超过了其余部分的时间限制。 是否有其他更快的算法来解决这个问题？

1
您可以假设 N ≤ 100000。 - Ivan Vergiliev
如果不需要使用C++，Python有集合、排列和重新排列（我认为它们的名称不同）。在Python中，您还可以对集合进行交集、并集和差集操作。如果您从未尝试过Python，请尝试一下，它非常适合数学计算。 - jokoon
4个回答
7
您的算法复杂度为O(N^2)，所以对于大小为10^5的数组来说，执行时间太长了。我尝试描述更好的解决方案：
我们有N个数字。让我们称倒置数组为I。解决这个问题，我们需要知道排列末尾仍然空闲的第K个位置在哪里（让我们称这个函数为F(K)）。首先，我们将数字N放到位置F(I[N]+1)，然后将数字N-1放到位置F(I[N-1]+1)，依此类推。

F可以按照以下方式计算：声明大小为N的数组M：1 1 1 ... 1，定义S(X) = M[1] + M[2] + ... + M[X]。 S被称为前缀和。 F(K)等于N加上1减去低于X的值，使得S(X) = K。每次我们将数字Z放置在位置N + 1 - X（对于K = I[Z] + 1）时，我们将零放置到M[X]。为了更快地找到X，我建议使用二进制索引树以O(logN)的时间计算前缀和，并使用二分查找查找与某个预定义值相等的S(X)。

这种算法的总复杂度为O(N(log(N))^2)。这是Ruby的实现（您可以在ideone中直接运行并检查输出，更改输入）：
# O(n(log(n))^2) solution for http://opc.iarcs.org.in/index.php/problems/FINDPERM

# Binary Indexed Tree (by Peter Fenwick)
# http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
class FenwickTree

  # Initialize array 1..n with 0s
  def initialize(n)
    @n = n
    @m = [0] * (n + 1)
  end

  # Add value v to cell i
  def add(i, v)
    while i <= @n
      @m[i] += v
      i += i & -i
    end
  end

  # Get sum on 1..i
  def sum(i)
    s = 0
    while i > 0
      s += @m[i]
      i -= i & -i
    end
    s
  end

  # Array size
  def n
    return @n
  end

end

# Classical binary search
# http://en.wikipedia.org/wiki/Binary_search_algorithm
class BinarySearch

  # Find lower index i such that ft.sum(i) == s
  def self.lower_bound(ft, s)
    l, r = 1, ft.n
    while l < r
      c = (l + r) / 2
      if ft.sum(c) < s
        l = c + 1
      else
        r = c
      end
    end
    l
  end

end

# Read input data
n = gets.to_i
q = gets.split.map &:to_i

# Initialize Fenwick tree
ft = FenwickTree.new(n)
1.upto(n) do |i|
  ft.add i, 1
end

# Find the answer
ans = [0] * n
(n - 1).downto(0) do |i|
  k = BinarySearch.lower_bound(ft, q[i] + 1)
  ans[n - k] = i + 1
  ft.add k, -1
end
puts ans.join(' ')

存在一种时间复杂度为 O(N(log(N))) 的解决方案。它使用了一种 二叉搜索树：我们在顶点上创建数字为 1, 2, 3, ... N 的 BST，然后我们可以通过值在 O(log(N)) 的时间内找到第 K 个数字，并且也可以在 O(log(N)) 的时间内删除顶点。
还有一种使用 std::set 的解决方案，但我现在想不出来。
附注：我还建议您阅读一些关于算法和奥林匹克竞赛的书籍，如Skienna（Programming Challenges）或Cormen（Introduction to Algorithms）。
附注2：非常抱歉之前描述的错误解决方案。
针对输入数据0 1 0 2 2 1 2 0，您的算法输出了0 4 5 2 7 1 3 8，而不是2 4 5 1 7 6 3 8，请问您能解释一下原因吗？ - 2147483647
非常抱歉，我的解决方案是错误的...让我再试着给你提供另一个。 - Aleksei Chernenkov
谢谢！在更改了您先前算法的一些部分之后，它已经可以工作了，但时间复杂度也变成了n^2。 - 2147483647
你的算法运行得很完美，但是它仍然和我最初的算法一样慢，我仍然只能得到70%的分数。 - 2147483647
是的，这是因为你的 get_x 函数需要 ~N 次操作才能执行 + 你调用了 N 次。所以结果是 O(N^2) 算法。但我建议你在二进制索引树上使用二分查找：请参见我上面的代码 - k = BinarySearch.lower_bound(ft, q[i] + 1) 每次调用需要 ~(log(N))^2 操作。我也调用了 N 次，因此总体复杂度为 O(N((LogN)^2))。 - Aleksei Chernenkov
3
最昂贵的部分显然是将高达100,000个元素移动到结果数组中。
如果您将该数组分成更多块，可以将其加速几倍。
例如，如果您有10个块并记住每个块的元素数量，则可以根据键选择要写入的正确块，然后只需为该块移动元素（最多少10次）。
新问题是如何在块之间实现良好的数字分布。
此外，您还可以使用链表：http://www.cplusplus.com/reference/stl/list/ 它非常适用于插入操作，但随机查找效率较低。但仍然可以通过查找x个元素来加快速度，这可能比在数组中移动x个元素更快。
然后，您可以使用组合方法，并具有多个指针的链表，因此您始终可以从最近的指针进行查找。
1
这也是一个不错的方法。如果您使用大小为sqrt(N)的块，可以获得O（Nsqrt(N))的解决方案... 这被称为sqrt分解。 - Aleksei Chernenkov
2

这里有一个非常好的算法以及所需的C++代码：

该问题是通过利用以下事实来解决的：如果在第7个位置有2，则在放置7之前留下两个空盒子。因此，如果8处为0，7处为2，则反向结果数组如下所示：8 _ _ 7 _ _ _ _。

现在，进行平方根分解并进行插入：

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n, k = 0, d, r, s, sum, temp, m, diff, check = 1;
    cin >> n;

    d = sqrt(n) + 1;
    int arr[n], result[n], indices[d], arr2[d][d], num = 1;

    for (int i = 0; i < n; i++)
        cin >> arr[i];               //The inversion sequence is accepted.

    for (int i = 0; i < d; i++)
        indices[i] = 0;              //Indices tell where to start counting from in each row.

    for (r = 0; r < d; r++)
    {
        for (s = 0; s < d; s++)
        {
            arr2[r][s] = num;       //Array is filled with 1 to n (after sqrt decomposition).
            num = num + 1;
            if (num == n+1)
            {
                check = 0; break;
            }
        }
        if (check == 0)
            break;
    }

    int l = s;
    while (l >= 0)                  //Non-Zero numbers are shifted to right and 0 placed in
    {                               //empty spaces.
        arr2[r][d-1 - k] = arr2[r][l];
        k = k + 1; l = l - 1;
    }

    k = d-1 - k + 1;
    for (int t = 0; t < k; t++)
        arr2[r][t] = 0;

    indices[r] = indices[r] + k;    //Index of the last row is shifted to first non-zero no.

    for (int i = n-1; i >= 0; i--)
    {
        sum = 0; m = 0;
        while (sum < arr[i] + 1)
        {
            sum = sum + (d - indices[m]); //Empty boxes in each row are counted.
            m = m + 1;
        }

        m = m - 1;
        sum = sum - (d - indices[m]);     //When sum = 1 + corresponding value in inversion
        diff = arr[i] + 1 - sum;          //sequence, then that particular value is made 0
        temp = indices[m] + diff - 1;     //and (that value - 1) is the index of the number
                                      //to be placed in result array.
        result[arr2[m][temp] - 1] = i+1;
        for (int w = temp - 1; w >= indices[m]; w--)
        {
            arr2[m][w + 1] = arr2[m][w];  //Then, 0 is shifted to just before non-zero number
        }                                 //in the row, and the elements are shifted right
        arr2[m][indices[m]] = 0;          //to complete the sort.
        indices[m] = indices[m] + 1;
    }                                     //This is done n times for 1 to n integers thus
                                      //giving the permutation in reverse order in result
    for (int p = n-1; p >= 0; p--)        //array.
        cout << result[p] << ' ';

    return 0;
}
1

你的算法对于这个问题来说不够高效，因为它的复杂度是O(n^2)，这意味着在某些输入情况下需要进行10^10次操作。你需要想出一种更便宜的解决方案。

我建议你使用以下算法（索引从1到N）：

for i=1 to N
   input a(i)
   if i==1 insert 1 into b
   else insert i into b at place i-a(i)
end
1
我建议你使用链表而不是数组来解决 b 的问题。 - orezvani
1
如果使用链表，那么这会产生一个O(n^2)的算法吗？ - Dialecticus
如果你计算插入的次数，它是O(n)。但如果你计算比较的次数，它是O(n^2)。 - orezvani
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接