可数性与数组的绝对不同计数

Question

所以我昨天参加了Codibility面试，今天被告知我没有通过，不幸的是Codibility和雇主都没有给我任何其他关于我在哪里出错的信息，所以我希望能得到一些帮助，让我知道哪里出错了。我知道Codibility非常重视程序运行的速度以及它对大量数据的行为。现在我没有复制粘贴问题，所以这大概是我记得的

1. 数一数数组a中绝对不同的元素的数目，这意味着如果数组中有-3和3，这些数字就不不同，因为|-3 |=| 3 |。我想举个例子会更清楚

a={-5，-3,0,1，-3} 结果是4，因为这个数组中有4个绝对不同的元素。

这个问题还指出a.length将是<；=10000，最重要的是它指出假设数组是按升序排序的，但我并不真正理解为什么我们需要对它进行排序

如果您认为我遗漏了什么，请提问，我将尝试进一步澄清问题。

这是我的代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;


public class test2 {

    int test(int[] a){
        Set<Integer> s=new HashSet<Integer>();

        for(int i=0;i<a.length;i++){
            s.add(Math.abs(a[i]));

        }
        return s.size();

    }

    public static void main(String[] args) {
        test2 t=new test2();
        int[] a={1,1,1,2,-1};
        System.out.println(t.test(a));

    }

}

Answer 1

这里有一个简单的解决方案。

public class test{

public static int dis(Integer[] arr) {
    out.println(Arrays.asList(arr));
    if (arr.length == 0) {
        return 0;
    }
    int i = 0;
    int j = arr.length - 1;
    int c = 0;
    while (i <= j) {
        if ((j != arr.length - 1) && (Math.abs(arr[j]) == Math.abs(arr[j + 1]))) {
            out.println("skipping J==" + j);
            j--; continue;
        }
        if ((i != 0) && (Math.abs(arr[i]) == Math.abs(arr[i - 1]))) {
            out.println("skipping I==" + i);
            i++; continue;
        }
        if (Math.abs(arr[i]) < Math.abs(arr[j])) {
            j--;
            c++;
        }
        else if (Math.abs(arr[i]) > Math.abs(arr[j])) {
            i++; c++;
        }
        else {
            i++; j--; c++;
        }

        out.println("I=" + i + " J=" + j + " C=" + c);
    }
    return c;
}




public static void main(String[] arg){

//Integer[] a = {34,2,3,4,3,-2,3};
//out.println("distinct elements are" + dis(a));
Integer[] aa={-5,-3,0,1,3};
out.println("distinct elements count " + dis(aa));
Integer[] ab={-5,-3,0,1,3, 4, 6, 7};
out.println("distinct elements count " + dis(ab));
Integer[] ac={-5};
out.println("distinct elements count " + dis(ac));
Integer[] acc={9};
out.println("distinct elements count " + dis(acc));
Integer[] ad={9,9,9};
out.println("distinct elements count " + dis(ad));
Integer[] ae={-5,-5};
out.println("distinct elements count " + dis(ae));
Integer[] aee={1,5,5,5,5};
out.println("distinct elements count " + dis(aee));
Integer[] af={-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8};
out.println("distinct elements count " + dis(af));

}

}

输出是

[-5, -3, 0, 1, 3]
distinct elements count 4
[-5, -3, 0, 1, 3, 4, 6, 7]
distinct elements count 7
[-5]
distinct elements count 1
[9]
distinct elements count 1
[9, 9, 9]
distinct elements count 1
[-5, -5]
distinct elements count 1
[1, 5, 5, 5, 5]
distinct elements count 2
[-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8]
distinct elements count 8

Answer 2

如果对数组进行排序，则可以通过查找邻居来查找重复项。要比较绝对值，需要从开始和结束都开始。这样可以避免创建新结构。

编辑：由于冲突，IMHO HashMap/HashSet是O（log（log（n））如果有一个完美的散列函数，那么它只有O（1）。我本以为在我的机器上创建对象的速度不会快得多，但似乎只有4倍。

总之，您可以看到使用集合更简单、更清晰、更易于维护。它仍然非常快，在98%的情况下是最好的解决方案。

public static void main(String[] args) throws Exception {
    for (int len : new int[]{100 * 1000 * 1000, 10 * 1000 * 1000, 1000 * 1000, 100 * 1000, 10 * 1000, 1000}) {
        int[] nums = new int[len];
        for (int i = 0; i < len; i++)
            nums[i] = (int) (Math.random() * (Math.random() * 2001 - 1000));
        Arrays.sort(nums);

        long timeArray = 0;
        long timeSet = 0;
        int runs = len > 1000 * 1000 ? 10 : len >= 100 * 1000 ? 100 : 1000;
        for (int i = 0; i < runs; i++) {
            long time1 = System.nanoTime();
            int count = countDistinct(nums);
            long time2 = System.nanoTime();
            int count2 = countDistinctUsingSet(nums);
            long time3 = System.nanoTime();
            timeArray += time2 - time1;
            timeSet += time3 - time2;
            assert count == count2;
        }
        System.out.printf("For %,d numbers, using an array took %,d us on average, using a Set took %,d us on average, ratio=%.1f%n",
                len, timeArray / 1000 / runs, timeSet / 1000 / runs, 1.0 * timeSet / timeArray);
    }
}

private static int countDistinct(int[] nums) {
    int lastLeft = Math.abs(nums[0]);
    int lastRight = Math.abs(nums[nums.length - 1]);
    int count = 0;
    for (int a = 1, b = nums.length - 2; a <= b;) {
        int left = Math.abs(nums[a]);
        int right = Math.abs(nums[b]);
        if (left == lastLeft) {
            a++;
            lastLeft = left;
        } else if (right == lastRight) {
            b--;
            lastRight = right;
        } else if (lastLeft == lastRight) {
            a++;
            b--;
            lastLeft = left;
            lastRight = right;
            count++;
        } else if (lastLeft > lastRight) {
            count++;
            a++;
            lastLeft = left;
        } else {
            count++;
            b--;
            lastRight = right;
        }
    }
    count += (lastLeft == lastRight ? 1 : 2);
    return count;
}

private static int countDistinctUsingSet(int[] nums) {
    Set<Integer> s = new HashSet<Integer>();
    for (int n : nums)
        s.add(Math.abs(n));
    int count = s.size();
    return count;
}

印刷品

对于100000000个数字，使用数组平均需要279623 us，使用集合平均需要1270029 us，比率=4.5

对于10000000个数字，使用数组平均需要28525 us，使用集合平均需要126591 us，比率=4.4

对于1000000个数字，使用数组平均占用2846 us，使用集合平均占用12131 us，比率=4.3

对于100000个数字，使用数组平均需要297us，使用集合平均需要1239us，比率=4.2

对于10000个数字，使用数组平均占用42 us，使用集合平均占用156 us，比率=3.7

对于1000个数字，使用数组平均需要8个us，使用集合平均需要30个us，比率=3.6

---

在@Kevin K的点上，即使是整数也可能发生冲突，即使它的散列值是唯一的，它也可以映射到同一个bucket，因为容量是有限的。

public static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public static void main(String[] args) throws Exception {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(32, 2.0f);
    for (int i = 0; i < 10000 && map.size() < 32 * 2; i++) {
        if (hash(i) % 32 == 0)
            map.put(i, i);
    }
    System.out.println(map.keySet());
}

印刷品

373，343，305，275，239，205，171，137，102，68，34，0]

值的顺序与此相反，因为哈希映射已生成LinkedList。

Answer 3

您应该注意数组是按升序排序的。

假设只有正数，或者问题不是关于绝对值的。

如果实际元素与上一个元素不同，则可以通过遍历列表来计算该数字，并将计数器增加一个。（第一个元素为+1）

如果您理解这一点，可以添加绝对非重复约束。例如，通过两个指针改进算法，一个从开始，一个从结束。然后还要注意两个指针的工作方式是并行的，这样两个指针都将以0或绝对最低值（正/负）结束-这会使整个事情复杂化一点，但这是可能的。