Java 计数元素排列检查
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22579054/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Counting Element Permutation check
提问by helpdesk
In the codility permutation check question:
在编码排列检查问题中：
A non-empty zero-indexed array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
is a permutation, but array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
is not a permutation.
The goal is to check whether array A is a permutation.
Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
For example, given array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
the function should return 1.
Given array A such that:
A[0] = 4
A[1] = 1
A[2] = 3
the function should return 0.
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Here is my solution to it, but I have an error. I feel, I need to check for one extra condition before the code can work well. When tested with an array like this: A[4,1,3}, it returned 1 instead of 0 . What else do I need to test for to get this code to work perfectly? I am missing it because I don't see why a[]{4,1,3} is NOT a permutation and why A[] {4,1,3,2} is a permutation in the question. If anyone could explain that, I might be able to solve my problem. Now,I did modify it to work now on my eclipse,tested but on codility, I still keep getting error about the line : counter[A[i]] += 1; Any one knows why this is so? Something that the array is out of bound but I didn't get that error on my eclipse IDE.
Thanks
这是我的解决方案，但我有一个错误。我觉得，在代码可以正常工作之前，我需要检查一个额外的条件。当使用这样的数组进行测试时：A[4,1,3}，它返回 1 而不是 0 。我还需要测试什么才能使此代码完美运行？我很想念它，因为我不明白为什么 a[]{4,1,3} 不是排列以及为什么 A[] {4,1,3,2} 是问题中的排列。如果有人可以解释这一点，我也许可以解决我的问题。现在，我确实将它修改为现在在我的 Eclipse 上工作，经过测试，但在编码方面，我仍然不断收到有关该行的错误：counter[A[i]] += 1；有谁知道为什么会这样？数组越界，但我的 Eclipse IDE 没有出现该错误。
谢谢
public class Solution {
/**
* @param args
*/
public static int solution(int[] A) {
// write your code in Java SE 7
int[] counter = new int[(A[0] * A.length)];
int max = -1;
int OccurBefore = -1; // store some random number for a start
for (int i = 0; i < A.length; i++) {
if (A[i] > max) {
max = A[i];
}
if (A[i] == OccurBefore) {
return 0;
}
if(A[i] != OccurBefore) {
OccurBefore = A[i];
counter[A[i]] += 1;
}
}
if(A.length<max){
return 0;
}
return 1;
}
}
回答by Salix alba
By definition of a permutation you need to have exactly one of each number, see https://en.wikipedia.org/wiki/Permutation
根据排列的定义，您需要每个数字都只有一个，请参阅https://en.wikipedia.org/wiki/Permutation
Try first with a doubly nested loop, this is not the required answer as it require O(N^2) complexity, but its the simplest algorithm.
首先尝试使用双重嵌套循环，这不是必需的答案，因为它需要 O(N^2) 复杂度，但它是最简单的算法。
One problem is you not using your counter array, you settting but not reading values. I can't quite understand why its size has A[0]*A.length. A[0] is not special as (3,2,4,1) or (1,2,3,4) could be valid permutations.
一个问题是你没有使用你的计数器数组，你设置而不是读取值。我不太明白为什么它的大小有 A[0]*A.length。A[0] 并不特殊，因为 (3,2,4,1) 或 (1,2,3,4) 可能是有效的排列。
回答by Porsche
The wording of the problem is kinda confusing. It actually wants you to check if the array contains 1..N integers (no duplicates or missing number).
这个问题的措辞有点令人困惑。它实际上希望您检查数组是否包含 1..N 个整数（没有重复或丢失的数字）。
class Solution {
public int solution(int[] A) {
// write your code in Java SE 7
int[] count = new int[A.length];
for (int i = 0; i < A.length; i++) {
int x = A[i]-1;
if (x >= A.length) return 0;
int check = count[x];
if (check > 0) return 0;
count[x] = 1;
}
return 1;
}
}
回答by MarkWillAnd
A couple things to improve your approach to this problem:
有几件事可以改善您解决此问题的方法：
The "max" variable isn't really necessary, as you can just compare the values of the array to the length of the array. If any of them exceed the length, you can just break out of program with a return of 0
I'm confused as to what you're trying to achieve with your "Counter" array. When you instantiate it, you're instantiating it with a length of length of A multiplied by A[0]. Considering A[0] could be any value (or in the example question A[0] can be 1,2,3,4) you can't really know what to expect as a length for your "counter" array. If you want a "counter" array that is the same length as the A array (which I used in my solution), use the following:
int[] counter = new int[A.length];The occurBefore concept is interesting, but you have to consider that the Array can be any length. So if we have an array of {2,3,2,4,5,6}, your occurBefore values will be 2, then you will compare 2 with 3, change occurBefore to 3 and then compare 2 to 3. Even though 2 exists twice in the array, your occurBefore comparison will never reveal this.
“max”变量并不是真正必要的，因为您可以将数组的值与数组的长度进行比较。如果其中任何一个超过了长度，你可以直接退出程序并返回 0
我对您尝试使用“计数器”数组实现的目标感到困惑。当你实例化它时，你是用长度 A 乘以 A[0] 来实例化它。考虑到 A[0] 可以是任何值（或者在示例问题中 A[0] 可以是 1,2,3,4），您无法真正知道“计数器”数组的长度是什么。如果您想要一个与 A 数组（我在我的解决方案中使用的）长度相同的“计数器”数组，请使用以下命令：
int[] counter = new int[A.length];发生之前的概念很有趣，但您必须考虑到 Array 可以是任意长度。因此，如果我们有一个 {2,3,2,4,5,6} 数组，则您的出现前值将为 2，然后您将 2 与 3 进行比较，将发生前更改为 3，然后将 2 与 3 进行比较。即使是 2在数组中存在两次，您的出现之前比较永远不会显示这一点。
Hint: you can use 2 for loops, one to populate an array with "legal" values, one to confirm the populated array contains the 1 -> N numbers that it would need to contain to be a valid permutation.
提示：您可以使用 2 个 for 循环，一个用“合法”值填充数组，一个确认填充的数组包含 1 -> N 个数字，它需要包含作为有效排列。
回答by tas
This works fine.
这工作正常。
- Sort array
- Check every pair of adjacent elements. If right element != left Element + 1,
- 排序数组
- 检查每对相邻元素。如果右元素 != 左元素 + 1，
then the array is not a permutation
那么数组不是排列
public class permutation {
public static void main(String[] args) {
int[] A={2,3,7,4,5,8,6,9,10,11};
Arrays.sort(A);
boolean perm = true;
for (int i=0; i<A.length-1; i++){
if(A[i+1]!= A[i]+1 ){
perm = false;
}
}
System.out.println(perm);
}
}
回答by Ajeet Singh
100% Result : PHP Code for PermCheck Codility
100% 结果：PermCheck Codility 的 PHP 代码
function solution($A) {
$count_of_elements = array_fill(0, count($A)+1, null);
for($i=0; $i < count($A); $i++ ){
if($A[$i] > count($A) || $A[$i] <= 0)
return 0;
$count_of_elements[$A[$i]] += 1;
if($count_of_elements[$A[$i]] > 1)
return 0;
}
if(array_sum($count_of_elements) < count($A))
return 0;
return 1;
}
回答by Ajeet Singh
100/% for PHP PermCheck Codility, Bit more optimized
PHP PermCheck Codility 100/%，稍微优化
function solution($A) {
$count_of_elements = array_fill(0, count($A)+1, null);
for($i=0; $i < count($A); $i++ ){
$count_of_elements[$A[$i]] += 1;
if($A[$i] > count($A) || $A[$i] <= 0 || $count_of_elements[$A[$i]] > 1)
return 0;
}
if(array_sum($count_of_elements) < count($A))
return 0;
return 1;
}
回答by dontHaveName
simple php 100/100 solution
简单的 php 100/100 解决方案
function solution($A) {
$count = count($A);
if (count(array_unique($A)) != $count) return 0;
$sum = array_sum($A);
$should_be = 0;
for ($i = 1; $i <= $count; $i++) {
$should_be += $i;
}
return intval($sum == $should_be);
}
回答by Asif Arshad
I've used Set for the solution:
我使用 Set 作为解决方案：
import java.util.*;
class Solution {
public int solution(int[] A) {
final Set perm = new HashSet();
final int size = A.length;
for(int number : A)
{
if(number > size)
return 0;
perm.add(number);
}
if(perm.size() == A.length)
return 1;
else
return 0;
}
}
回答by Samlik
This is a Scala solution that gets 100/100. Find it more elegant in Scala
这是一个获得 100/100 的 Scala 解决方案。在 Scala 中发现它更优雅
object Solution {
def solution(A: Array[Int]): Int = {
if (A.max == A.length && A.distinct.size == A.length)
1
else
0
}
}
回答by moxi
This solution scores 100 in codility:
此解决方案在可编码性方面得分 100：
/**
* https://codility.com/demo/results/demoYEU94K-8FU/ 100
*/
public class PermCheck {
public static final int NOT_PERMUTATION = 0;
public static final int PERMUTATION = 1;
// (4,1,3,2) = 1
// (4,1,3) = 0
// (1) = 1
// () = 1
// (2) = 0
public int solution(int[] A) {
// write your code in Java SE 8
int[] mark = new int[A.length + 1];
for (int i = 0; i < A.length; ++i) {
int value = A[i];
if(value >= mark.length) {
return NOT_PERMUTATION;
}
if(mark[value] == 0) {
mark[value]=1;
} else {
return NOT_PERMUTATION;
}
}
return PERMUTATION;
}
}
You can also see it here: https://github.com/moxi/codility-lessons/blob/master/Codility/CountingElements/PermCheck.javaalong with some others.
您也可以在此处查看：https: //github.com/moxi/codility-lessons/blob/master/Codility/CountingElements/PermCheck.java以及其他一些内容。
