时间戳

首页 > 解决方案 > 使用 hashmap 比较两个数组

java - 使用 hashmap 比较两个数组

问题描述

所以我在codewar上遇到了一个编码问题。该指令是“给定两个数组 a 和 b 编写一个函数 comp(a, b) (orcompSame(a, b)) 来检查两个数组是否具有“相同”的元素，具有相同的多重性。“相同”的意思是，在这里，无论顺序如何，b 中的元素都是平方中的元素。

示例 有效数组 a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [121, 14641, 20736, 361, 25921, 361, 20736, 361] comp(a, b) 返回 true，因为在 b 中，121 是 11 的平方，14641 是 121 的平方，20736 是 144 的平方，361 是 19 的平方，25921 是 161 的平方，以此类推。如果我们用正方形来写 b 的元素，那就很明显了：

a = [121, 144, 19, 161, 19, 144, 19, 11] b = [11 11, 121 121, 144 144, 19 19, 161 161, 19 19, 144 144, 19 19] 无效数组如果，例如，我们将第一个数字更改为其他数字，comp 可能不再返回 true：

a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [132, 14641, 20736, 361, 25921, 361, 20736, 361] comp(a,b) 返回 false 因为在 b 132不是任意数量 a 的平方。

a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [121, 14641, 20736, 36100, 25921, 361, 20736, 361] comp(a,b) 返回 false 因为在 b 36100不是任意数量 a 的平方。

备注 a 或 b 可能是 []（除 R、Shell 之外的所有语言）。a 或 b 可能为 nil 或 null 或 None 或无（C++​​、Elixir、Haskell、PureScript、Pascal、R、Rust、Shell 除外）。如果 a 或 b 为 nil（或 null 或 None），则问题没有意义，因此返回 false。”

这是我的解决方案

import java.util.HashMap;

公共类主{

public static int BiggestElement(int [] arr) {
    int result = 0;
    result = arr[0];
    for(int i=0;i<arr.length;i++) {
        if(arr[i]>= result) {
            result = arr[i];
        }
    }
    
    return result;
}

public static boolean comp(int[] a, int []b) {
    int size = a.length;
    if(a.length != b.length) {
        System.out.println("They don't have the same size");
        return false;
    }
    else {
        //First we need to check which one has the biggest element
        int biggestA = 0;
        int biggestB = 0;
        System.out.println(biggestA = BiggestElement(a));
        System.out.println(biggestB = BiggestElement(b));
        
        //creating two maps 
        HashMap<Integer, Integer> map1 = new HashMap<Integer,Integer>();
        HashMap<Integer, Integer> map2 = new HashMap<Integer,Integer>();
        //now we put every value of b inside the map
        for(int i = 0; i<a.length;i++) {
            map1.put(a[i], i);
            map2.put(b[i], i);
        }
        
        //now we do the actual comparision
        if(biggestA>biggestB) {
            for(int  i=0;i<size;i++) {
                if(!map1.containsKey(b[i]*b[i])) {
                    return false;
                }
            }
        } else {
            for(int  i=0;i<size;i++) {
                if(!map2.containsKey(a[i]*a[i])) {
                    System.out.println("map 1 doesn't contain " + (b[i]*b[i]));
                    return false;
                }
            }
        }
        
    }
    return true;
}

public static void main(String[] args) {
    int[] a = new int[]{121, 144, 19, 161, 19, 144, 19, 11};
    int[] b = new int[]{121, 14641, 20736, 361, 25921, 361, 20736, 361};
    
    System.out.println(comp(a,b));
}

}

我提交了我的代码，他们做了 13 次测试，但我失败了 3 次。任何人都向我提出任何建议或解决方案，以便我可以改进它。

标签： javaarraysdata-structureshashmap

解决方案

关于您上面的方法，您依靠映射键来跟踪数组值。但是，地图不能有重复的键，因此每当您为给定的键向地图添加值时，旧的都会被替换。

因此，以下数组将同等比较（它们不是 - 其中一个应该4s是.b16

int[] a = {1,2,2,3,4,4}; 
int[] b = {1,4,4,9,16,4};

好吧，这是一种方法。我相当肯定还有其他可能更有效。要点是它会记录每次出现的值，并将该计数用作比较过程的一部分。

  • 首先，检查以确保数组不为空，并且长度与任何例程可能会这样做的长度相同。
  • 然后找到哪个数组有正方形（尽管在调用该方法之前应该知道这一点）。
  • 然后计算每个平方n出现的次数。
  • 然后对于每个值n，从值计数中减去 1。
  • 如果该值变为负数，则立即返回 false，因为不存在一对一映射。
  • 否则，通过这些值运行，如果有任何非零，则返回 false。
public static boolean comp(int[] a, int[] b) {

    if (a == null || b == null ||
            (a.length != b.length)) {
                   return false;
    }

    int maxVal = Integer.MIN_VALUE;
    int maxSquare = Integer.MIN_VALUE;
    for(int i = 0; i < vals.length; i++) {
        maxVal = Math.max(vals[i], maxVal);
        maxSquare = Math.max(squares[i], maxSquare);
    }
    // swap them if required
    if (maxVal > maxSquare) {
        int[] temp = squares;
        squares = vals;
        vals = temp;
    }
    Map<Integer, Integer> mapA = new HashMap<>();
    for (int el : a) {
        mapA.compute(el * el, (k, v) -> v == null ? 1 : v + 1);
    }
    
    for (int el : b) {
        if (mapA.computeIfPresent(el, (k, v) -> v - 1) < 0) {
            return false;
        }
    }
    
    for (int i : mapA.values()) {
        if (i != 0) {
            return false;
        }
    }
    return true;
    
}

推荐阅读