如何判断一个数组是否是O（n）中的一个置换？
input：包含从1到N的整数值的N个元素的只读数组（某些整数值可以多次出现！）。 和一个固定大小的存储区（10,100,1000等 – 不依赖于N）。
如何判断O（n）是否代表排列？
– 我到目前为止所取得的成绩（答案certificate这不好）： –
- 我使用有限的内存区域来存储数组的总和和乘积。
- 我把这个和与N *（N + 1）/ 2和N的乘积进行比较！
我知道，如果条件（2）是真的，我可能有一个排列。 我想知道是否有办法certificate条件（2）足以说明我是否有一个置换。 到目前为止，我还没有想出这个…
我非常怀疑有一个解决scheme。 你的问题似乎与几年前在math文献中提出的问题非常接近， 这里给出了一个总结（“重复检测问题”，S. Kamal Abdali，2003） ，它使用循环检测 – 这个想法如下：
如果存在重复，则存在1到N之间的数字j ，以致于以下将导致无限循环：
x := j; do { x := a[x]; } while (x != j);
因为置换由一个或多个不同元素s 0 ，s 1 ，… s k-1的子集S组成，其中对于1和k-1之间的所有j，s j = a [s j-1 ] = a [s k-1 ]，所以所有的元素都被包含在循环中 – 其中一个副本不会是这个子集的一部分。
例如，如果数组= [2,1,4,6,8,7,9,3,8]
那么在位置5处粗体的元素是重复的，因为所有其他元素形成循环：{2-> 1,4-> 6-> 7 – > 9 – > 8 – > 3}。 而arrays[2,1,4,6,5,7,9,3,8]和[2,1,4,6,3,7,9,5,8]是有效的排列（周期为{2 1→4→6→7→9→8→3,5→和2→1,4→6→7→9→8→5→3）分别）。
Abdali进入寻找重复的方式。 基本上下面的algorithm（使用弗洛伊德的循环寻找algorithm ），如果你遇到一个重复的问题：
function is_duplicate(a, N, j) { /* assume we've already scanned the array to make sure all elements are integers between 1 and N */ x1 := j; x2 := j; do { x1 := a[x1]; x2 := a[x2]; x2 := a[x2]; } while (x1 != x2); /* stops when it finds a cycle; x2 has gone around it twice, x1 has gone around it once. If j is part of that cycle, both will be equal to j. */ return (x1 != j); }
难点是我不确定你所说的问题是否与他论文中的问题相符，我也不确定他描述的方法是以O（N）运行还是使用固定的空间。 一个潜在的反例如下：
[3,4,5,6,7,8,9,10，… N-10，N-9，N-8，N-7，N-2，N-5，N-5，N- 3，N-5，N-1，N，1,2]
其基本上是身份置换移位了2，元素[N-6，N-4和N-2]由[N-2，N-5，N-5]代替。 这有正确的总和（不是正确的产品，但我拒绝把产品作为一种可能的检测方法，因为用任意精度algorithm计算N！的空间要求是O（N），这违反了“固定存储空间”要求），如果你试图find循环，你会得到循环{3-> 5-> 7-> 9 – > … N-7 – > N-5 – > N-1}和{4 – > 6→8→… N-10→N-8→N-2→N→2}。 问题是可能会有N个周期（身份置换有N个周期），每个周期占用O（N）来find一个副本，并且必须跟踪哪些周期已被跟踪，哪些没有。 我怀疑是否可以在固定的空间内做到这一点。 但也许是。
这是一个足够严重的问题，这是值得问mathoverflow.net （尽pipe事实上，大部分时间mathoverflow.net被引用在stackoverflow这是太容易的问题）
编辑：我曾经问过mathoverflow ，这里有一些有趣的讨论。
在O（1）空间中这是不可能的，至less使用单扫描algorithm。
certificate
假设你已经处理了N个元素的N / 2个。 假设序列是一个置换，那么给定algorithm的状态，你应该能够找出N / 2个剩余元素的集合。 如果你不能弄清楚剩余的元素，那么可以通过重复一些旧的元素来愚弄algorithm。
有N个selectN / 2个可能的剩余集合。 它们中的每一个都必须由algorithm的不同内部状态来表示，否则就无法找出剩余的元素。 但是，需要对数空间来存储X个状态，所以需要BigTheta（log（NselectN / 2））空间来存储N个selectN / 2个状态。 该值随N增长，因此algorithm的内部状态不能适应O（1）空间。
更正式的certificate
你想创build一个程序P，它给出了最后的N / 2元素和线性时间常数空间algorithm处理N / 2个元素后的内部状态，确定整个序列是否是1的置换。 .N。 这个中学课程没有时间和空间。
假设P存在，我们可以创build一个程序Q，只取决于线性时间常数空间algorithm的内部状态，它决定了序列的最终N / 2个元素（如果它是一个置换）。 Q通过传递每个可能的最后N / 2个元素并返回P返回true的集合。
但是，因为Q有N个selectN / 2个可能的输出，所以至less有N个selectN / 2个可能的input。 这意味着原始algorithm的内部状态必须存储至lessN个selectN / 2个状态，需要BigTheta（logNselectN / 2），这大于常量大小。
因此，具有时间和空间界限的原始algorithm如果具有恒定的内部状态，也不能正确地工作。
[我认为这个想法是可以概括的，但思维不能certificate。]
后果
BigTheta（log（NselectN / 2））等于BigTheta（N）。 因此，只要使用布尔数组并且在遇到它们时勾选值（可能）是空间最优的，并且因为需要线性时间，所以也是时间最优的。
我怀疑你能certificate这一点;）
(1, 2, 4, 4, 4, 5, 7, 9, 9)
我认为更一般地说，这个问题是不能通过按顺序处理数字来解决的。 假设你正在按顺序处理元素，并且你在数组的一半。 现在你的程序的状态必须以某种方式反映你到目前为止遇到的数字。 这需要至lessO（n）位来存储。
这是不行的，因为复杂性是作为N而不是M的函数给出的，意味着N >> M
这是我的注意事项，但是为了使bloomfilter有用，你需要一个大的M，在这一点上，你可以使用简单的位来切换像整数
http://en.wikipedia.org/wiki/Bloom_filter
对数组中的每个元素运行k个哈希函数检查是否包含在布隆filter中如果存在，那么就有可能看到之前的元素如果不是，则添加它
当你完成后，你可以将它与1..N数组的结果进行比较，因为这只会让你花费另一个N.
现在，如果我没有提出足够的警告，那么它不是100％，甚至是近似的，因为你在N中指定了复杂度，这意味着N >> M，从根本上说它不会像你指定的那样工作。
顺便说一下，个别项目的假阳性率应为e = 2 ^（ – m /（n * sqrt（2）））
哪个瞎猜会给你一个想法，M大概需要被接受。
我不知道如何在O（N）中做，或者即使它可以在O（N）中完成。 我知道如果你（使用适当的）sorting和比较，它可以在O（N log N）中完成。
这就是说，有许多O（N）技术可以做，以表明一个不是另一个的排列。
- 检查长度。 如果不平等，显然不是一个排列。
- 创build异或指纹。 如果XOR所有元素的值不匹配，那么它不能是一个置换。 一场比赛将是不确定的。
- find所有元素的总和。 虽然结果可能会溢出，但匹配这个“指纹”时不应该担心。 但是，如果你做了一个涉及乘法的校验和，那么溢出将是一个问题。
希望这可以帮助。
你可能可以通过计算sum(x_i)和product(x_i)以一系列不同的随机select的大小为O(n)常数C，在随机O(n)时间和恒定空间中做到这一点。 这基本上让你围绕product(x_i)变得太大的问题。
然而，如果sum(x_i)=N(N+1)/2和product(x_i)=N! 是保证排列的充分条件，非排列产生假阳性的机会是多less（我希望每个C你都希望〜1 / C，但是可能不会）。
当且仅当在数组中没有重复的值时，它是一个排列，应该很容易检查在O（N）
根据你有多less空间，相对于N，你可以尝试使用哈希和桶。
也就是说，迭代整个列表，散列每个元素，并将其存储在一个存储桶中。 您需要find一种方法来减less哈希中的桶碰撞，但这是一个解决的问题。
如果一个元素试图进入一个与它相同的项目的桶，它是一个排列。
这种types的解决scheme将是O（N），因为您只触摸每个元素一次。
然而，问题在于空间M是否大于N。 如果M> N，这个解决scheme会很好，但是如果M <N，那么你将无法以100％的精度解决问题。
首先，这是可能的信息理论原因。 我们可以平均检查数组中的数字是否在O（N）时间和O（1）空间的范围内。 要指定任何这样的入境数字数组，需要N log N位的信息。 但是指定一个置换大约需要(N log N) - N位信息（斯特林逼近）。 因此，如果我们可以在testing过程中获取N位信息，我们可能会知道答案。 这在N次中是微不足道的（事实上，在M静态空间中，我们可以很容易地获取每一步的log M信息，在特殊情况下我们可以获取log N信息）。
另一方面，我们只能在我们的静态存储空间中存储诸如M log N比特的信息，这可能大大低于N ，因此决定表面的形状在“置换”与“不”。
我认为这几乎是可能的，但没有完全给出问题设置。 我认为人们应该使用循环技巧（如尤利安所提到的链接），但是手中有一个尾巴的关键假设在这里失败了，因为你可以用排列索引数组的最后一个元素。
总和和产品将不能保证正确的答案，因为这些哈希是碰撞，即不同的input可能会产生相同的结果。 如果你想要一个完美的哈希，一个单数的结果，实际上完全描述了数组的数值组成，它可能是以下内容。
想象一下，对于[1, N]范围内的任意数字i ，可以产生一个唯一的素数P(i) （例如， P(i)是第i个素数）。 现在你需要做的就是计算数组中所有数字的所有P(i)的乘积。 该产品将完全和明确地描述您的数组的组成，忽略其中的值的sorting。 所有你需要做的是预先计算“完美”的值（对于一个置换），并将其与给定input的结果进行比较:)
当然，这样的algorithm并不能立即满足公布的要求。 但是同时它也是非常通用的：它可以让你检测数组中绝对的任意数字组合的排列。 在你的情况下，你需要检测一个特定组合1, 2, ..., N的排列。 也许这可以以某种方式被用来简化的事情…可能不是。
好吧，这是不同的，但它似乎工作！
我跑了这个testing程序（C＃）：
static void Main(string[] args) { for (int j = 3; j < 100; j++) { int x = 0; for (int i = 1; i <= j; i++) { x ^= i; } Console.WriteLine("j: " + j + "\tx: " + x + "\tj%4: " + (j % 4)); } }
简短解释：x是单个列表的所有XOR的结果，i是特定列表中的元素，j是列表的大小。 由于我所做的只是XOR，所以元素的顺序并不重要。 但是，我正在考虑在应用这个时候正确的排列。
如果你看j％4，你可以对这个值进行切换，得到如下的结果：
bool IsPermutation = false; switch (j % 4) { case 0: IsPermutation = (x == j); break; case 1: IsPermutation = (x == 1); break; case 2: IsPermutation = (x == j + 1); break; case 3: IsPermutation = (x == 0); break; }
现在我承认这可能需要一些微调。 这不是100％，但是这是一个很好的入门方法。 也许在XOR循环中运行一些小的检查，这可能是完美的。 尝试从那里开始。
它看起来像要求在堆栈机中查找重复的数组。
当你提取每个数字，并且知道已经被取出的数字的时候，听起来不可能知道堆栈的完整历史。
这是certificate不能做的事情：
假设通过一些技巧，除了最后一个单元之外，你没有发现任何重复。 然后，问题将减less到检查最后一个单元是否包含重复。
如果到目前为止您没有问题状态的结构化表示，那么您将被缩减为在整个先前的input上对每个单元执行线性search。 很容易看到这是如何使用二次时间algorithm。
现在，假设通过一些聪明的数据结构，你实际上知道你期望最后看到哪个数字。 那么当然，这种知识至less需要足够的位来存储你所寻找的数字 – 也许是一个存储单元？ 但倒数第二和倒数第二个问题：那么你必须类似地代表一组两个可能的数字，但尚未被看到。 这当然需要比编码只有一个剩余的数字更多的存储空间。 通过类似的论点，除非你愿意接受二次最坏的情况，否则国家的规模必须随着问题的规模而增长。
这是时间的权衡。 你可以有二次时间和恒定的空间，或者线性时间和线性空间。 你不能有线性时间和恒定的空间。
看看下面的解决scheme。 它使用O（1） 额外的空间。 它在检查过程中改变了数组，但是在最后返回到它的初始状态。
这个想法是：
- 检查是否有任何元素超出范围[1，n] => O（n）。
-
按顺序遍历数字（现在所有数字都保证在[1，n]的范围内），并且对于每个数字x（例如3）：
- 去第x个单元格（例如a [3]），如果它是否定的，那么在你之前有人已经访问过它=>不是排列。 否则（a [3]是正数），乘以-1。 => O（n）。
- 遍历数组并取消所有负数。
这样，我们确信所有元素都在[1，n]范围内，并且没有重复=>数组是一个置换。
int is_permutation_linear(int a[], int n) { int i, is_permutation = 1; // Step 1. for (i = 0; i < n; ++i) { if (a[i] < 1 || a[i] > n) { return 0; } } // Step 2. for (i = 0; i < n; ++i) { if (a[abs(a[i]) - 1] < 0) { is_permutation = 0; break; } a[i] *= -1; } // Step 3. for (i = 0; i < n; ++i) { if (a[i] < 0) { a[i] *= -1; } } return is_permutation; }
这是testing它的完整程序：
/* * is_permutation_linear.c * * Created on: Dec 27, 2011 * Author: Anis */ #include <stdio.h> int abs(int x) { return x >= 0 ? x : -x; } int is_permutation_linear(int a[], int n) { int i, is_permutation = 1; for (i = 0; i < n; ++i) { if (a[i] < 1 || a[i] > n) { return 0; } } for (i = 0; i < n; ++i) { if (a[abs(a[i]) - 1] < 0) { is_permutation = 0; break; } a[abs(a[i]) - 1] *= -1; } for (i = 0; i < n; ++i) { if (a[i] < 0) { a[i] *= -1; } } return is_permutation; } void print_array(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%2d ", a[i]); } } int main() { int arrays[9][8] = { { 1, 2, 3, 4, 5, 6, 7, 8 }, { 8, 6, 7, 2, 5, 4, 1, 3 }, { 0, 1, 2, 3, 4, 5, 6, 7 }, { 1, 1, 2, 3, 4, 5, 6, 7 }, { 8, 7, 6, 5, 4, 3, 2, 1 }, { 3, 5, 1, 6, 8, 4, 7, 2 }, { 8, 3, 2, 1, 4, 5, 6, 7 }, { 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 8, 4, 2, 1, 3, 5, 6 } }; int i; for (i = 0; i < 9; i++) { printf("array: "); print_array(arrays[i], 8); printf("is %spermutation.\n", is_permutation_linear(arrays[i], 8) ? "" : "not "); printf("after: "); print_array(arrays[i], 8); printf("\n\n"); } return 0; }
其输出：
array: 1 2 3 4 5 6 7 8 is permutation. after: 1 2 3 4 5 6 7 8 array: 8 6 7 2 5 4 1 3 is permutation. after: 8 6 7 2 5 4 1 3 array: 0 1 2 3 4 5 6 7 is not permutation. after: 0 1 2 3 4 5 6 7 array: 1 1 2 3 4 5 6 7 is not permutation. after: 1 1 2 3 4 5 6 7 array: 8 7 6 5 4 3 2 1 is permutation. after: 8 7 6 5 4 3 2 1 array: 3 5 1 6 8 4 7 2 is permutation. after: 3 5 1 6 8 4 7 2 array: 8 3 2 1 4 5 6 7 is permutation. after: 8 3 2 1 4 5 6 7 array: 1 1 1 1 1 1 1 1 is not permutation. after: 1 1 1 1 1 1 1 1 array: 1 8 4 2 1 3 5 6 is not permutation. after: 1 8 4 2 1 3 5 6
下面的Java解答部分回答问题。 我相信时间复杂度是O（n）。 （这种信念基于事实，即解决scheme不包含嵌套循环。）关于记忆 – 不确定。 问题首先出现在谷歌的相关请求，所以它可能是有用的有人。
public static boolean isPermutation(int[] array) { boolean result = true; array = removeDuplicates(array); int startValue = 1; for (int i = 0; i < array.length; i++) { if (startValue + i != array[i]){ return false; } } return result; } public static int[] removeDuplicates(int[] input){ Arrays.sort(input); List<Integer> result = new ArrayList<Integer>(); int current = input[0]; boolean found = false; for (int i = 0; i < input.length; i++) { if (current == input[i] && !found) { found = true; } else if (current != input[i]) { result.add(current); current = input[i]; found = false; } } result.add(current); int[] array = new int[result.size()]; for (int i = 0; i < array.length ; i ++){ array[i] = result.get(i); } return array; } public static void main (String ... args){ int[] input = new int[] { 4,2,3,4,1}; System.out.println(isPermutation(input)); //output true input = new int[] { 4,2,4,1}; System.out.println(isPermutation(input)); //output false }
int solution(int A[], int N) { int i,j,count=0, d=0, temp=0,max; for(i=0;i<N-1;i++) { for(j=0;j<Ni-1;j++) { if(A[j]>A[j+1]) { temp = A[j+1]; A[j+1] = A[j]; A[j] = temp; } } } max = A[N-1]; for(i=N-1;i>=0;i--) { if(A[i]==max) { count++; } else { d++; } max = max-1; } if(d!=0) { return 0; } else { return 1; } }
