1

这是我的第一篇文章，希望它符合网站的发布指南。首先感谢所有社区：几个月来读你并学到了很多:o)

前提：我是 IT 的一年级学生。

这是问题：我正在寻找一种有效的方法来计算给定正 int 数组（这就是我所知道的）中唯一对的数量（恰好出现两次的数字），例如，如果：

int[] arr = {1,4,7,1,5,7,4,1,5};

arr 中唯一对的数量为 3 (4,5,7)。

我在...评估我的提案的效率时遇到了一些困难，比方说。

这是我做的第一个代码：

int numCouples( int[] v ) {
int res = 0;
int count = 0;
for (int i = 0 ; i < v.length; i++){
    count = 0;
    for (int j = 0; j < v.length; j++){
        if (i != j && v[i] == v[j]){
            count++;
        }
    }
    if (count == 1){
        res++;
    }
}
return res/2;
}

这不应该是好的，因为它检查整个给定数组的次数与给定数组中元素的数量一样多......如果我错了，请纠正我。

这是我的第二个代码：

int numCouples( int[] v) {
int n = 0;
int res = 0;
for (int i = 0; i < v.length; i++){
    if (v[i] > n){
        n = v[i];
    }
}
int[] a = new int [n];
for (int i = 0; i < v.length; i++){
    a[v[i]-1]++;
}
for (int i = 0; i < a.length; i++){
    if (a[i] == 2){
        res++;
    }
}
return res;
}

我想这应该比第一个更好，因为它只检查给定数组的 2 次和 n 数组的 1 次，当 n 是给定数组的最大值时。如果 n 很大，我猜可能不太好......

嗯，2个问题：

  1. 我是否理解如何“衡量”代码的效率？

  2. 有更好的方法来计算给定数组中唯一对的数量吗？

编辑：该死的我刚刚发布，我已经被答案淹没了！谢谢！我会仔细研究每一个，暂时我说我没有得到那些涉及 HashMap 的内容：在我的知识范围内（因此再次感谢您的洞察力：o））

4

9 回答 9

3 
public static void main(String[] args) {
    int[] arr = { 1, 4, 7, 1, 5, 7, 4, 1, 5 };

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i = 0; i < arr.length; i++) {
        Integer count = map.get(arr[i]);
        if (count == null)
            map.put(arr[i], 1);
        else
            map.put(arr[i], count + 1);
    }

    int uniqueCount = 0;

    for (Integer i : map.values())
        if (i == 2)
            uniqueCount++;

    System.out.println(uniqueCount);
}
于 2013-02-07T10:34:52.557 回答
2

好吧，这是您的两个问题的另一个答案：

am I understanding good how to "measure" the efficiency of the code?

有多种方法可以衡量代码的效率。首先，人们区分记忆效率和时间效率。计算所有这些值的常用方法是了解算法构建块的效率。看看维基。

例如，使用快速排序进行排序需要n*log(n)操作。遍历数组只需要n操作，其中n是输入中的元素数。

there's a better way to count the number of unique pairs in a given array?

这是您的另一种解决方案。这个复杂性将是：，O(n*log(n)+n)Big O 符号在哪里。O(...)

import java.util.Arrays;

public class Ctest {
  public static void main(String[] args) {
    int[] a = new int[] { 1, 4, 7, 1, 7, 4, 1, 5, 5, 8 };
    System.out.println("RES: " + uniquePairs(a));
  }

  public static int uniquePairs(int[] a) {
    Arrays.sort(a);
    // now we have: [1, 1, 1, 4, 4, 5, 5, 7, 7]

    int res = 0;
    int len = a.length;
    int i = 0;

    while (i < len) {
      // take first number
      int num = a[i];
      int c = 1;
      i++;

      // count all duplicates
      while(i < len && a[i] == num) {
        c++;
        i++;
      }
      System.out.println("Number: " + num + "\tCount: "+c);
      // if we spotted number just 2 times, increment result
      if (c == 2) {
        res++;
      }
    }

    return res;
  }
}
于 2013-02-07T11:14:10.530 回答
1 
int [] a = new int [] {1, 4, 7, 1, 7, 4, 1, 5, 1, 1, 1, 1, 1, 1};
Arrays.sort (a);

int res = 0;
for (int l = a.length, i = 0; i < l - 1; i++)
{
    int v = a [i];
    int j = i + 1;
    while (j < l && a [j] == v) j += 1;
    if (j == i + 2) res += 1;
    i = j - 1;
}

return res;
于 2013-02-07T10:26:12.743 回答
1 
public static void main(String[] args) {
    int[] arr = {1,4,7,1,7,4,1,5};
    Map<Integer, Integer> counts = new HashMap<Integer,Integer>();
    int count = 0;

    for(Integer num:arr){
        Integer entry = counts.get(num);

        if(entry == null){
            counts.put(num, 1);
        }else if(counts.get(num) == 1){
            count++;
            counts.put(num, counts.get(num) + 1);
        }
    }

    System.out.println(count);

}
于 2013-02-07T10:33:22.283 回答
0

您可以使用 HashMap 轻松分组。这是我的代码。

int[] arr = {1,1,1,1,1,1,4,7,1,7,4,1,5};
    HashMap<Integer,Integer> asd = new HashMap<Integer, Integer>();
    for(int i=0;i<arr.length;i++)
    {
        if(asd.get(arr[i]) == null)
        {
            asd.put(arr[i], 1);
        }
        else
        {
            asd.put(arr[i], asd.get(arr[i])+1);
        }
    }

    //print out
    for(int key:asd.keySet())
    {
        //get pair
        int temp = asd.get(key)/2;
        System.out.println(key+" have : "+temp+" pair");
    }

添加用于检查唯一对，您可以删除打印出来的一个

//unique pair
    for(int key:asd.keySet())
    {
        if(asd.get(key) == 2)
        {
            System.out.println(key+" are a unique pair");
        }
    }
于 2013-02-07T10:29:21.833 回答
0

一段时间后，另一个解决方案应该很好用。

public getCouplesCount(int [] arr) {
    int i = 0, i2;
    int len = arr.length;
    int num = 0;
    int curr;
    int lastchecked = -1;

    while (i < len-1) {
        curr = arr[i];
        i2 = i + 1;
        while (i2 < len) {
            if (curr == arr[i2] && arr[i2] != lastchecked) {
                num++; // add 1 to number of pairs
                lastchecked = curr; 
                i2++; // iterate to next
            } else if (arr[i2] == lastchecked) {
                // more than twice - swap last and update counter
                if (curr == lastchecked) {
                    num--;
                }
                // swap with last
                arr[i2] = arr[len-1];
                len--;
            } else {
                i2++;
            }
        i++;
    }

return num;
}

我不确定它是否有效，但它比首先对数组进行排序或使用哈希图更有效......

于 2013-02-07T11:19:34.980 回答
0 
var sampleArray = ['A','B','C','D','e','f','g'];
 var count = 0;
 for(var i=0; i<=sampleArray.length; i++) {
    for(var j=i+1; j<sampleArray.length; j++) {
        count++;
        console.log(a[i] ,',', a[j]);
    }
 }
 console.log(count);

这是我尝试过的简单方法。

于 2020-06-01T13:44:46.470 回答
0

使用 ConcurrentHashMap 的 Java8 并行流版本

int[] arr = {1,4,7,1,5,7,4,1,5};
Map<Integer,Long> map=Arrays.stream(arr).parallel().boxed().collect(Collectors.groupingBy(Function.identity(),
        ConcurrentHashMap::new,Collectors.counting()));
map.values().removeIf(v->v!=2);
System.out.println(map.keySet().size());
于 2020-06-01T14:09:13.193 回答
0 
 #include <bits/stdc++.h>
 using namespace std;
 int main() 
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int arr[9] = {1,4,7,1,5,7,4,1,5};    // given array
    int length=9;                        // this should be given
    int count=0;
    map<int,int> m;
    for(int i=0;i<length;i++)
        m[arr[i]]++;
    cout<<"List of unique pairs : ";
    for(auto it=m.begin();it!=m.end();it++)
        if(it->second==2)
        {
            count++;
            cout<<it->first<<" ";
        }
    cout<<"\nCount of unique pairs(appears exactly twice) : "<<count;
    return 0;
 }

 OUTPUT :
 List of unique pairs : 4 5 7 
 Count of unique pairs(appears exactly twice) : 3

 Time Complexity : O(N) where N is the number of elements in array
 Space Complexity : O(N) total no. of unique elements in array always <=N
于 2020-10-08T20:04:15.157 回答