问题描述:

I've been trying to write this reduce method and I can't find a nice way to do it in java. I managed in python but it makes use of lots of python stuff and porting that to java seems like a real pain. Is there a more java way to do it?

Here's some test code, that should show what I mean if the title wasn't clear.

My python test code:

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])

which you can run here: https://repl.it/EthR/0

And some Java test code for you which you can run here 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);}

}

}

网友答案:

Not sure about "nice", but it works:

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;
}
网友答案:

So you want to test if an array is a smaller array repeated - now if, by your definition, bigArray.length % smallArray.length != 0 means that it is NOT the smaller array repeated, I can give you a solution. In other words: If the smaller array doesn't fit inside the bigger array an even number of times, does that mean that it is NOT the smaller array repeated? If that's true, try this:

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;
}

If this solution doesn't fit your needs, comment on my answer and I'll try to think of something else. It's late right now, though, otherwise I'd do so right now ^^
(Note that I've never done anything with Python, so I didn't bother trying to understand your code)

网友答案:

How about this? Return value is 0 = not a duplicate, 1 = same, 2 = repeated once, 3 = repeated twice etc

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;
}

It's also O(n) because we only have to go through the largest array once to determine the number of duplicates :)

相关阅读:
Top