ArrayList 与 HashMap 时间复杂度

Question

场景如下：

您有 2 个字符串 (s1, s2) 并且想要检查一个是否是另一个的排列，因此您生成了 s1 的所有排列并存储它们，然后迭代并与 s2 进行比较，直到找到其中一个与否。

现在，在这种情况下，我正在考虑在严格考虑时间复杂度时使用 ArrayList 还是 HashMap 更好，因为我相信两者都有 O(N) space复杂性。

根据 javadoc，ArrayList 的搜索复杂度为 O(N)，而 HashMap 为 O(1)。如果是这种情况，是否有任何理由赞成在这里使用 ArrayList 而不是 HashMap 因为 HashMap 会更快？

我能想到的唯一潜在缺点是，如果您在 key = value，即 {k = "ABCD", v = "ABCD"} 等地方做一些事情，您的 (k,v) 对可能会有点奇怪。

Answer 1

如图here:

import java.io.*; 
import java.util.*; 
  
class GFG{ 
      
    static int NO_OF_CHARS = 256; 
      
    /* function to check whether two strings 
    are Permutation of each other */
    static boolean arePermutation(char str1[], char str2[]) 
    { 
        // Create 2 count arrays and initialize 
        // all values as 0 
        int count1[] = new int [NO_OF_CHARS]; 
        Arrays.fill(count1, 0); 
        int count2[] = new int [NO_OF_CHARS]; 
        Arrays.fill(count2, 0); 
        int i; 
   
        // For each character in input strings, 
        // increment count in the corresponding 
        // count array 
        for (i = 0; i <str1.length && i < str2.length ; 
                                                 i++) 
        { 
            count1[str1[i]]++; 
            count2[str2[i]]++; 
        } 
   
        // If both strings are of different length. 
        // Removing this condition will make the program  
        // fail for strings like "aaca" and "aca" 
        if (str1.length != str2.length) 
            return false; 
   
        // Compare count arrays 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count1[i] != count2[i]) 
                return false; 
   
        return true; 
    } 
   
    /* Driver program to test to print printDups*/
    public static void main(String args[]) 
    { 
        char str1[] = ("geeksforgeeks").toCharArray(); 
        char str2[] = ("forgeeksgeeks").toCharArray(); 
          
        if ( arePermutation(str1, str2) ) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
} 
  
// This code is contributed by Nikita Tiwari.

如果您执着于实现，请使用 HashSet，它仍然有 O(1) 查找时间，只是没有键

Answer 2

您可以使用 HashSet，因为您只需要一个参数。

ArrayList 与 HashMap 时间复杂度

ArrayList vs HashMap time complexity

java

arraylist

hashmap

time-complexity