How efficiently to check if two arrays are similar?-CodePudding

You can only swap maximum 1 time 2 elements of an array.

My code is working but I don't know how to make my code faster. I need it to be executed in 3s.

boolean checkSimilarArray(int[] a, int[] b) {
    int sml = 0;
    boolean result = false;
    for (int i = 0; i<a.length; i  ){
        if (a[i]!= b[i]){
            sml  ;
        }
    }
    Arrays.sort(a);
    Arrays.sort(b);
    if(Arrays.equals(a,b)){
        if (sml <= 2){
            result = true;
        }else{
            result = false;
        }
    }
    return result;
}

CodePudding user response：

If by similar means you have same count of elements and same elements with same or different order you may just create a simple checksum using xor.

public class MyClass {
    static boolean checkSimilarArray(int[] a, int[] b) {
        int testa= 0;
        int testb = 0;
        for (int i=0; i < a.length; i  ) {
            testa ^= a[i];
            testb ^= b[i];
        }
        
        return testa == testb;
    }

    public static void main(String args[]) {
        int[] a = new int[] {1,2,3, 5,6,7};
        int[] b = new int[] {1,3,2, 6, 5, 7};
        boolean ok = false;
        ok = MyClass.checkSimilarArray(a, b);
        System.out.println(ok);
    }
}

assume the length is exactly the same. No sort needed also, also the algorithm can be further improved since it won't catch all edge case scenarios but answers the problem genesis.

CodePudding user response：

If you are not confortable with XOR you can just store the differences for each array and iterate over them from the front and back at the same time to check if they match, this is still O(n) as the differences arrays will at most have 2 elements:

boolean checkSimilarArray(int[] a, int[] b) {
    int aLength = a.length;
    int bLength = b.length;
    if (aLength != bLength) {
        return false;
    }
    
    List<Integer> aDiffs = new ArrayList<>();
    List<Integer> bDiffs = new ArrayList<>();
    for (int i = 0; i < aLength; i  ) {
        if (a[i] != b[i]) {
            if (aDiffs.size() == 2) {
                return false;
            }
            aDiffs.add(a[i]);
            bDiffs.add(b[i]);
        }
    }
    
    int bDiffsSize = bDiffs.size();
    for (int i = 0; i < aDiffs.size(); i  ) {
        if (!aDiffs.get(i).equals(bDiffs.get(bDiffsSize - i - 1))) {
            return false;
        }
    }
    
    return true;
}