java 如何在Java中找到数组的最小覆盖前缀？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5627966/
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
How can I find the smallest covering prefix of an array in Java?
提问by Raj
Find the first covering prefix of a given array.
A non-empty zero-indexed array A consisting of N integers is given. The first covering prefix of array A is the smallest integer P such that and such that every value that occurs in array A also occurs in sequence.
For example, the first covering prefix of array A with A[0]=2, A[1]=2, A[2]=1, A[3]=0, A[4]=1 is 3, because sequence A[0], A[1], A[2], A[3] equal to 2, 2, 1, 0 contains all values that occur in array A.
找到给定数组的第一个覆盖前缀。
给出了一个由 N 个整数组成的非空零索引数组 A。数组 A 的第一个覆盖前缀是最小的整数 P，使得数组 A 中出现的每个值也依次出现。
例如数组A的第一个覆盖前缀A[0]=2, A[1]=2, A[2]=1, A[3]=0, A[4]=1 是3，因为序列A[0], A[1], A[2], A[3] 等于 2, 2, 1, 0 包含数组 A 中出现的所有值。
My solution is
我的解决方案是
int ps ( int[] A )
{
int largestvalue=0;
int index=0;
for(each element in Array){
if(A[i]>largestvalue)
{
largestvalue=A[i];
index=i;
}
}
for(each element in Array)
{
if(A[i]==index)
index=i;
}
return index;
}
But this only works for this input, this is not a generalized solution.
但这仅适用于此输入，这不是通用解决方案。
回答by dopplesoldner
Got 100% with the below.
得到 100% 以下。
public int ps (int[] a)
{
var length = a.Length;
var temp = new HashSet<int>();
var result = 0;
for (int i=0; i<length; i++)
{
if (!temp.Contains(a[i]))
{
temp.Add(a[i]);
result = i;
}
}
return result;
}
回答by corsiKa
I would do this
我会这样做
int coveringPrefixIndex(final int[] arr) {
Map<Integer,Integer> indexes = new HashMap<Integer,Integer>();
// start from the back
for(int i = arr.length - 1; i >= 0; i--) {
indexes.put(arr[i],i);
}
// now find the highest value in the map
int highestIndex = 0;
for(Integer i : indexes.values()) {
if(highestIndex < i.intValue()) highestIndex = i.intValue();
}
return highestIndex;
}
回答by Juvanis
Your question is from Alpha 2010 Start Challengeof Codility platform. And here is my solution which got score of 100. The idea is simple, I track an array of counters for the input array. Traversing the input array backwards, decrement the respective counter, if that counter becomes zero it means we have found the first covering prefix.
您的问题来自Alpha 2010 Start Challengeof Codility 平台。这是我的解决方案，得分为100。这个想法很简单，我跟踪输入数组的计数器数组。向后遍历输入数组，递减相应的计数器，如果该计数器变为零，则表示我们已找到第一个覆盖前缀。
public static int solution(int[] A) {
int size = A.length;
int[] counters = new int[size];
for (int a : A)
counters[a]++;
for (int i = size - 1; i >= 0; i--) {
if (--counters[A[i]] == 0)
return i;
}
return 0;
}
回答by Krzysiek
100p
100p
public static int ps(int[] a) {
Set<Integer> temp = new HashSet<Integer>();
int p = 0;
for (int i = 0; i < a.length; i++) {
if (temp.add(a[i])) {
p = i+1;
}
}
return p;
}
回答by Renato
here's my solution in C#:
这是我在 C# 中的解决方案：
public static int CoveringPrefix(int[] Array1)
{
// Step 1. Get length of Array1
int Array1Length = 0;
foreach (int i in Array1) Array1Length++;
// Step 2. Create a second array with the highest value of the first array as its length
int highestNum = 0;
for (int i = 0; i < Array1Length; i++)
{
if (Array1[i] > highestNum) highestNum = Array1[i];
}
highestNum++; // Make array compatible for our operation
int[] Array2 = new int[highestNum];
for (int i = 0; i < highestNum; i++) Array2[i] = 0; // Fill values with zeros
// Step 3. Final operation will determine unique values in Array1 and return the index of the highest unique value
int highestIndex = 0;
for (int i = 0; i < Array1Length; i++)
{
if (Array2[Array1[i]] < 1)
{
Array2[Array1[i]]++;
highestIndex = i;
}
}
return highestIndex;
}
回答by Jan
You can try this solution as well
你也可以试试这个解决方案
import java.util.HashSet;
import java.util.Set;
class Solution {
public int ps ( int[] A ) {
Set set = new HashSet();
int index =-1;
for(int i=0;i<A.length;i++){
if(set.contains(A[i])){
if(index==-1)
index = i;
}else{
index = i;
set.add(A[i]);
}
}
return index;
}
}
回答by user85421
Without using any Collection:
search the index of the first occurrence of each element,
the prefix is the maximum of that index. Do it backwards to finish early:
不使用任何集合：
搜索每个元素第一次出现的索引，
前缀是该索引的最大值。向后做以尽早完成：
private static int prefix(int[] array) {
int max = -1;
int i = array.length - 1;
while (i > max) {
for (int j = 0; j <= i; j++) { // include i
if (array[i] == array[j]) {
if (j > max) {
max = j;
}
break;
}
}
i--;
}
return max;
}
// TEST
private static void test(int... array) {
int prefix = prefix(array);
int[] segment = Arrays.copyOf(array, prefix+1);
System.out.printf("%s = %d = %s%n", Arrays.toString(array), prefix, Arrays.toString(segment));
}
public static void main(String[] args) {
test(2, 2, 1, 0, 1);
test(2, 2, 1, 0, 4);
test(2, 0, 1, 0, 1, 2);
test(1, 1, 1);
test(1, 2, 3);
test(4);
test(); // empty array
}
回答by Bernard Banta
This is what I tried first. I got 24%
这是我首先尝试的。我有 24%
public int ps ( int[] A ) {
int n = A.length, i = 0, r = 0,j = 0;
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
if ((long) A[i] == (long) A[j]) {
r += 1;
}
if (r == n) return i;
}
}
return -1;
}
回答by HelpVampire666
//method must be public for codility to access
public int solution(int A[]){
Set<Integer> set = new HashSet<Integer>(A.length);
int index= A[0];
for (int i = 0; i < A.length; i++) {
if( set.contains(A[i])) continue;
index = i;
set.add(A[i]);
}
return index;
}
this got 100%, however detected time was O(N * log N) due to the HashSet. your solutions without hashsets i don't really follow...
这得到了 100%，但是由于 HashSet，检测到的时间是 O(N * log N)。你没有哈希集的解决方案我真的没有遵循......
回答by HelpVampire666
shortest code possible in java:
java中可能的最短代码：
public static int solution(int A[]){
Set<Integer> set = new HashSet<Integer>(A.length);//avoid resizing
int index= -1; //value does not matter;
for (int i = 0; i < A.length; i++)
if( !set.contains(A[i])) set.add(A[index = i]); //assignment + eval
return index;
}
