时间戳

首页 > 解决方案 > 查找数组中是否存在多个非连续重复

java - 查找数组中是否存在多个非连续重复

问题描述

[c,a,a,b,b,d], [c,a,b,b,d,d,a] 或 [a,a,b,b,c,d,d] 应该返回 false 而 [ a,a,c,d,b,b] 或 [a,a,c,b,b​​,d] 应返回 true，因为重复项不连续。

public boolean findNSeqDup(String[] arr) {
    if(arr.length < 4){
        return false;
    }

    boolean isPrevDup = false;
    String prevString = "";
    for (int i = 0; i < arr.length; i++){
        if(arr[i].equals(prevString) && isPrevDup==true){
            System.out.println("true");
            return true;
        }
        else if(arr[i].equals(prevString) && isPrevDup==false){
            isPrevDup = true;
            prevString = "";
        }
        else if(!prevString.equals("") && !arr[i].equals(prevString)){
            prevString = "";
        }
        // for the first condition if the previous string is empty
        else {
            prevString = "";
        }
        prevString = arr[i];
    }
    System.out.println("false");
    return false;
}

上面的代码对所有应该返回假的条件都返回真（[c,a,a,b,b,d], [c,a,b,b,d,d,a] 或 [a,a,b ,b,c,d,d])。我究竟做错了什么？如果我使用堆栈或类似的数据结构，这会更容易吗？

标签： javaarrays

解决方案

似乎使用堆栈/双端队列来收集连续重复和单打的计数可以帮助解决此任务：

public static boolean findNonConsDup(String ... arr) {
    int n = arr.length;
    if(n < 4) {
        return false;
    }
    
    System.out.println(Arrays.toString(arr) + ": "); // debug print
    
    Deque<Integer> freqs = new ArrayDeque<>();
    String prev = arr[0];
    int cnt = 1;
    int prevFreq;
    
    for (int i = 1; i < n; i++) {
        if (!prev.equals(arr[i])) { // non-consecutive element found            
            if (freqs.isEmpty()) {
                freqs.push(cnt);
            }
            else {
                prevFreq = freqs.peek();
                // store the count of elements only when a single changes the duplicate or vice versa
                if (cnt == 1 && prevFreq > 1 || cnt > 1 && prevFreq == 1) {
                    freqs.push(cnt);
                    // early detection of non-consecutive duplicates
                    if (freqs.size() > 2) {
                        int p1 = freqs.pop();
                        int p2 = freqs.pop();
                        int p3 = freqs.pop();
                        // pattern found: at least 1 single separator between 2 duplicates
                        if (p1 > 1 && p2 == 1 && p3 > 1) {
                            return true;
                        } else { // restore queue
                            freqs.push(p3);
                            freqs.push(p2);
                            freqs.push(p1);
                        }
                    }
                }
            }
            cnt = 1;
        } else {
            cnt++;
        }
        prev = arr[i];
    }
    prevFreq = freqs.peek();
    if (cnt == 1 && prevFreq > 1 || cnt > 1 && prevFreq == 1) {
        freqs.push(cnt);
    }
    System.out.print(freqs + " -> "); // debug print
    return freqs.size() > 2 && freqs.pop() > 1 && freqs.pop() == 1 && freqs.pop() > 1;
}

测试：

public static void main(String args[]) {
  System.out.println(findNonConsDup("c","a","b","d","a","d"));
  System.out.println(findNonConsDup("c","a","b","b","a","d"));
  System.out.println(findNonConsDup("c","a","b","b","b", "a","d", "d"));

  System.out.println(findNonConsDup("c","a","a","b","b","d"));
  System.out.println(findNonConsDup("c","a","b","b","d","d","a"));
  System.out.println(findNonConsDup("a","a","b","b","c","d","d"));
  System.out.println(findNonConsDup("c", "a","a","c","d","b","d","d"));
  System.out.println(findNonConsDup("a","a","c","d","b","d","d"));
  System.out.println(findNonConsDup("a","a","c","b","b","d","d"));
}

输出

[c, a, b, d, a, d]: [1] -> false
[c, a, b, b, a, d]: [1, 2, 1] -> false
[c, a, b, b, b, a, d, d]: [2, 1, 3, 1] -> true
[c, a, a, b, b, d]: [1, 2, 1] -> false
[c, a, b, b, d, d, a]: [1, 2, 1] -> false
[a, a, b, b, c, d, d]: [2, 1, 2] -> true
[c, a, a, c, d, b, d, d]: [2, 1, 2, 1] -> true
[a, a, c, d, b, d, d]: [2, 1, 2] -> true
[a, a, c, b, b, d, d]: true

推荐阅读