排列的绝对绝对计数 - c#

所以我昨天参加了Codility面试，今天被告知我失败了，不幸的是，我没有得到Codility或雇主提供的关于我搞砸的任何其他信息，所以我很乐意为您提供帮助。我知道codility非常重视程序的运行速度以及其在大量情况下的行为。现在我没有复制粘贴问题，所以这大概是我记得的

计算数组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));

    }

}

参考方案

如果数组已排序，则可以通过查找高度来找到重复项。为了比较绝对值，需要从头到尾都开始。这样可以避免创建新的结构。

编辑:恕我直言，HashMap / HashSet由于冲突而为O(log(log(n))，如果有完善的哈希函数，它仅为O(1)。我本来以为不创建对象的速度要快得多，但是看起来在我的机器上快4倍。

总之，您可以看到使用Set更简单，更清晰并且更易于维护。它仍然非常快，在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;
}

版画

对于100,000,000个数字，使用数组平均花费279,623 us，使用Set平均花费1,270,029 us，比率= 4.5

对于10,000,000个数字，使用数组平均花费28,525 us，使用Set则平均花费126,591 us，比率= 4.4

对于1,000,000个数字，使用数组平均需要2,846 us，使用Set平均需要12,131 us，比率= 4.3

对于100,000个数字，使用数组平均花费297 us，使用Set则平均花费1,239 us，比率= 4.2

对于10,000个数字，使用数组平均花费42 us，使用Set平均花费156 us，比率= 3.7

对于1,000个数字，使用数组平均花费8 us，使用Set则平均花费30 us，比率= 3.6

就@Kevin K而言，即使Integer的哈希值是唯一的，即使Integer也会发生冲突，由于容量有限，它可以映射到同一存储桶。

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());
}

版画

[2032，2002，1972，1942，1913，1883，1853，1823，1763，1729，1703，1669，1642，1608，1582，1548，1524，1494，1456，1426，1405，1375，1337，1307，1255 ，1221、1187、1153、1134、1100、1066、1032、1016、986、956、926、881、851、821、791、747、713、687、653、610、576、550、516、508、478 ，440、410、373、343、305、275、239、205、171、137、102、68、34、0]

值是相反的，因为HashMap已生成到LinkedList中。

C＃Linq可空INT字段包含在List <int>中SQL转换 - c#

我有一张表格，其中列出了需要管理员签名的表单，而我想要做的就是将表单列表过滤到他们可以签名的表单。我得到了他们所管理的员工列表，然后将其放入员工ID列表中。var staffIds = manager.Staff.Select(x => x.Id).ToList(); 然后，我使用人员列表过滤表单列表。我得到了所有与经过身份验证的组织ID相匹配的表单，…

与哪些运算符>>兼容 - java

我这里没有什么代码int b=3; b=b >> 1; System.out.println(b); 它可以完美工作，但是当我将变量b更改为byte，short，float，double时，它包含错误，但是对于变量int和long来说，它可以完美工作，为什么它不能与其他变量一起工作？ 参考方案 位移位运算符（例如>>）与任何整数类型兼…

在PHP中使用long int - php

我正在尝试此方法，但无法存储较大的价值$var = rand(100000000000000,999999999999999); echo $var; // prints a 9 digit value(largest possible) 如何获得期望值？ 参考方案 PHP整数通常为32位。其他软件包提供了更高精度的整数：http://php.net/man…

将List <int>作为Javascript函数的参数传递 - javascript

我想接受List作为javascript函数的参数。我从后面的代码中调用此函数。并将一个List传递给函数。但是我在调​​用函数时得到了“ System.Collections.Generic.List`1 [System.Int32]”作为参数值。函数调用时我应该怎么做才能得到列表。我的代码是：Default.aspx.csprotected void P…

为什么我的按位运算不能在Java中与`int`一起使用？ - java

我刚得到以下编译器错误：./package/path/FrameScreenPosition.java:80: incompatible types found : int required: boolean if (frame.getExtendedState() & Frame.MAXIMIZED_BOTH) { ^ “扩展状态”是各种不同状态的…