关于 leetcode No.345 问题

Question

bobo老师, 我用了2种解法, 但是leetcode 给出的运行性能报告和预期的不太符合， 下面是我的分析，还请老师指点下

解法一

class Solution {
    public String reverseVowels(String s) {
        char[] vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

        int l = 0, r = s.length() - 1;

        char[] sCharArray = s.toCharArray();
        while (l < r) {
            boolean left = isVowel(vowels, s.charAt(l));
            boolean right = isVowel(vowels, s.charAt(r));

            if (left && right) {
                char temp = sCharArray[l];
                sCharArray[l++] = sCharArray[r];
                sCharArray[r--] = temp;
            }

            if (!left) {
                l++;
            }

            if (!right) {
                r--;
            }
        }

        return String.valueOf(sCharArray);
    }

    
    private boolean isVowel(char[] vowels, char value) {
        for (int i = 0; i < vowels.length; i++) {
	        if (vowels[i] == value) {
	            return true;
	        }
        }
        return false;
    }
}

解法二

class Solution {
    public String reverseVowels(String s) {
        Set<Character> charSet = new TreeSet<>();
        charSet.add('a');
        charSet.add('e');
        charSet.add('i');
        charSet.add('o');
        charSet.add('u');
        charSet.add('A');
        charSet.add('E');
        charSet.add('I');
        charSet.add('O');
        charSet.add('U');

        int l = 0, r = s.length() - 1;

        char[] sCharArray = s.toCharArray();
        while (l < r) {
            boolean left = isVowel(charSet, s.charAt(l));
            boolean right = isVowel(charSet, s.charAt(r));

            if (left && right) {
                char temp = sCharArray[l];
                sCharArray[l++] = sCharArray[r];
                sCharArray[r--] = temp;
            }

            if (!left) {
                l++;
            }

            if (!right) {
                r--;
            }
        }

        return String.valueOf(sCharArray);
    }

    
  private boolean isVowel(Set<Character> characters, char value) {
    return characters.contains(value);
  }
}

分析

• 我认为在解法1中, 应该是要慢于 解法2 的, 因为在判断 isVowel()方法在查找是否属于元音字母时, 是从 0 开始遍历 元音字符集, 所以我认为这里应该是比 用 Set<> 慢的
• Set<> 的 contains方法是基于红黑树的查找, 按理要比从 0 index 遍历要快的?
• 还是说leetcode的测试用例给的不全，有些运气的成分在其中？

Answer 1

liuyubobobo 2024-04-18 09:41:51

对于十个数据这个量级，静态数组远远快于红黑树。红黑树的复杂度虽然是 O(logn) 的，但是每一个操作都比对数组的直接操作更耗时。你可以理解成红黑树的 O(logn) 实际是 T(Alogn)，数组的 O(n) 实际是 T(Bn)。A 是大于 B 的，在 n 较小的情况下，红黑树是没有优势的。

也正是因为这个原因，在我的课程中，比如对于排序算法，我们在数据量较小的时候，可以使用插入排序这种 O(n^2) 级别的算法来优化归并排序这种 O(nlogn) 的算法，就是这个原因。

不过也正是因为 n 较小，讨论这个时间差异其实意义没有那么大。从算法面试的角度，通常不会关注这个性能差异的。因为这不是算法这一领域考察的重点。另外，值得一提的是，在我看来，更好的做法是建立一个长度为 256 的 bool 静态数组，将元音字符 ascii 值对应的位置设为 true，其他为 false，直接使用这个数组判断元音。相当于是哈希表的思路，但使用静态数组直接使用真正的 O(1) 的操作完成（而没有哈希表的冲突处理过程。）

继续加油！：）

• 提问者 Screenly #1

  非常感谢！leetcode小白受教了，哈哈