Schöne Art und Weise in Java, um herauszufinden, ob eine Liste / Array tatsächlich ein kleineres Array wiederholt - Java, Python, Arrays, Algorithmus, Liste

Ich habe versucht, diese Reduktionsmethode zu schreiben undIch finde keinen guten Weg, das in Java zu tun. Ich habe es in Python geschafft, aber es nutzt eine Menge Python-Zeug, und das nach Java zu portieren, scheint ein wirklicher Schmerz zu sein. Gibt es einen besseren Weg, das in Java zu tun?

Hier ist ein Testcode, der zeigen soll, was ich meine, wenn der Titel nicht klar ist.

Mein Python-Testcode:

def reduce_(duplicated):
def get_factors(n):
return set(reduce(list.__add__,
([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

factors = sorted(list(get_factors(len(duplicated))))
for factor in factors:
chunks = set([tuple(duplicated[i:i + factor]) for i in xrange(0, len(duplicated), factor)])
if len(chunks) == 1:
return list(chunks.pop())
return duplicated


def verify(expected, duplicated):
try:
result = reduce_(duplicated)
assert (expected == result)
print expected, "passed"
except AssertionError:
print "expected", expected, "!=", duplicated

#should return the same
verify([1, 2, 3], [1,2,3])
verify([1,2], [1,2])
verify([1,1,2], [1,1,2])
verify([5,8,8], [5,8,8])
verify([8], [8])
verify([1,8,1], [1,8,1])
verify([5,2,2,5], [5,2,2,5])
verify([5,5,2,2], [5,5,2,2])

# repeated only once
verify([1, 2, 3], [1,2,3,1,2,3])
verify([1,2], [1,2,1,2])
verify([1,1,2], [1,1,2,1,1,2])
verify([5,8,8], [5,8,8,5,8,8])
verify([8], [8,8])
verify([1,8,1], [1,8,1,1,8,1])
verify([5,2,2,5], [5,2,2,5,5,2,2,5])
verify([5,5,2,2], [5,5,2,2,5,5,2,2])

# repeated twice
verify([1, 2, 3], [1,2,3,1,2,3,1,2,3])
verify([1,2], [1,2,1,2,1,2])
verify([1,1,2], [1,1,2,1,1,2,1,1,2])
verify([5,8,8], [5,8,8,5,8,8,5,8,8])
verify([8], [8,8,8])
verify([1,8,1], [1,8,1,1,8,1,1,8,1])
verify([5,2,2,5], [5,2,2,5,5,2,2,5,5,2,2,5])
verify([5,5,2,2], [5,5,2,2,5,5,2,2,5,5,2,2])

was du hier laufen kannst: https://repl.it/EthR/0

Und etwas Java-Testcode für Sie, den Sie hier ausführen können https://www.compilejava.net/

    import java.util.*;

public class HelloWorld
{

public static <T> T[] reduce(T[] duplicated)
{
return duplicated; // implement me!
}

// arguments are passed using the text field below this editor
public static void main(String[] args)
{
// should return the same
verify(new Integer[]{1, 2, 3}, new Integer[]{1,2,3});
verify(new Integer[]{1,2}, new Integer[]{1,2});
verify(new Integer[]{1,1,2}, new Integer[]{1,1,2});
verify(new Integer[]{5,8,8}, new Integer[]{5,8,8});
verify(new Integer[]{8}, new Integer[]{8});
verify(new Integer[]{1,8,1}, new Integer[]{1,8,1});
verify(new Integer[]{5,2,2,5}, new Integer[]{5,2,2,5});
verify(new Integer[]{5,5,2,2}, new Integer[]{5,5,2,2});

// repeated only once
verify(new Integer[]{1, 2, 3}, new Integer[]{1,2,3,1,2,3});
verify(new Integer[]{1,2}, new Integer[]{1,2,1,2});
verify(new Integer[]{1,1,2}, new Integer[]{1,1,2,1,1,2});
verify(new Integer[]{5,8,8}, new Integer[]{5,8,8,5,8,8});
verify(new Integer[]{8}, new Integer[]{8,8});
verify(new Integer[]{1,8,1}, new Integer[]{1,8,1,1,8,1});
verify(new Integer[]{5,2,2,5}, new Integer[]{5,2,2,5,5,2,2,5});
verify(new Integer[]{5,5,2,2}, new Integer[]{5,5,2,2,5,5,2,2});

// repeated twice
verify(new Integer[]{1, 2, 3}, new Integer[]{1,2,3,1,2,3,1,2,3});
verify(new Integer[]{1,2}, new Integer[]{1,2,1,2,1,2});
verify(new Integer[]{1,1,2}, new Integer[]{1,1,2,1,1,2,1,1,2});
verify(new Integer[]{5,8,8}, new Integer[]{5,8,8,5,8,8,5,8,8});
verify(new Integer[]{8}, new Integer[]{8,8,8});
verify(new Integer[]{1,8,1}, new Integer[]{1,8,1,1,8,1,1,8,1});
verify(new Integer[]{5,2,2,5}, new Integer[]{5,2,2,5,5,2,2,5,5,2,2,5});
verify(new Integer[]{5,5,2,2}, new Integer[]{5,5,2,2,5,5,2,2,5,5,2,2});
}


public static <T> void verify(final T[] expected, final T[] duplicated)
{
if (expected == null || duplicated == null) throw new ComparisonException("Cannot be null");

final T[] result = reduce(duplicated);

if (result == null) throw new ComparisonException("Cannot be null");

if (expected.length != result.length)
{
throw new ComparisonException("lengths do not match in " + Arrays.toString(expected) + " and " + Arrays.toString(result));
}

for (int i = 0; i < expected.length; i++)
{
if (!result[i].equals(expected[i]))
{
throw new ComparisonException("Elem [" + i + "] does not match in " + Arrays.toString(expected) + " and " + Arrays.toString(result));
}
}

System.out.println(Arrays.toString(expected) + " passed: " + Arrays.toString(result));
}

public static class ComparisonException extends RuntimeException
{
public ComparisonException(String message){ super(message);}
}
}

Antworten:

Ich bin nicht sicher, ob ich "nett" bin, aber es funktioniert:

public static <T> T[] reduce(T[] duplicated)
{
int len = duplicated.length;
for (int i = 1; i <= len / 2; i++) {
if (len % i == 0) {
if (checkFactors(i, duplicated)) {
return Arrays.copyOf(duplicated, i);
}
}
}
return duplicated;
}

public static <T> boolean checkFactors(int factor, T[] arr) {
int len = arr.length;
for (int j = 1; j < len / factor; j++) {
if (!rangeCompare(j * factor, factor, arr)) {
return false;
}
}
return true;
}

public static <T> boolean rangeCompare(int off, int len, T[] arr) {
for (int i = 0; i < len; i++) {
if (!arr[i].equals(arr[off + i])) {
return false;
}
}
return true;
}

Sie möchten also testen, ob ein Array ein kleineres Array ist, das wiederholt wird. bigArray.length % smallArray.length != 0 bedeutet, dass es NICHT das kleinere Array wiederholt,Ich kann Ihnen eine Lösung geben. Mit anderen Worten: Wenn das kleinere Array nicht mehrmals in das größere Array passt, bedeutet dies, dass es NICHT das kleinere Array wiederholt? Wenn dies zutrifft, versuchen Sie Folgendes:

public boolean isArrayAnotherArrayRepeated(ArrayType[] bigArray, ArrayType[] smallType) {
double numberOfTimesSmallFitsInBig = bigArray.length / smallArray.length;
if (numberOfTimesSmallFitsInBig % 1 == 0)
{
//checks the condition mentioned above, i.e. that small doesn"t fit into big an even number of times
return false;
}
for (int i = 0; i < (int) numberOfTimesSmallFitsInBig; i++)
{
for (int h = 0; h < smallArray.length; h++)
{
if (smallArray[h] != bigArray[i+h]) {
//note that you may have to use .equals here, if you don"t want to compare references or primitive data types.
//that would then look like "if (!smallArray[h].equals(bigArray[i+h]))"
return false;
}
}
}
return true;
}

Wenn diese Lösung nicht Ihren Anforderungen entspricht, kommentieren Sie meine Antwort und ich werde versuchen, mir etwas anderes auszudenken. Es ist allerdings gerade spät, sonst würde ich es jetzt tun ^^
(Beachten Sie, dass ich noch nie etwas mit Python gemacht habe, also habe ich nicht versucht, Ihren Code zu verstehen.)

Wie wäre es damit? Der Rückgabewert ist 0 = kein Duplikat, 1 = dasselbe, 2 = einmal wiederholt, 3 = zweimal wiederholt usw

public int FindDuplicates(Integer[] a, Integer[] b)
{
int bigIndex = 0;
int smallIndex = 0;
int duplicates = 0;

if(b.length % a.length == 0)
while(bigIndex < b.length)
{
if(a[smallIndex] == b[bigIndex])
{
bigIndex++;
smallIndex++;
if(smallIndex == a.length)
{
smallIndex = 0;
duplicates++;
}
}
else
{
duplicates = 0;
break;
}
}

return duplicates;
}

Es ist auch O (n), weil wir das größte Array nur einmal durchlaufen müssen, um die Anzahl der Duplikate zu bestimmen :)