1

これは私の最初の投稿です。サイトの投稿ガイドラインに準拠していることを願っています。まず最初に、すべてのコミュニティに感謝します: 数か月にわたってあなたを読んで、多くのことを学びました :o)

前提: 私は IT の 1 年生です。

質問は次のとおりです。指定された正の int 配列内の一意のペア (正確に 2 回表示される数値) の数を効率的にカウントする方法を探しています (それが私が知っているすべてです)。たとえば、次の場合:

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

これは、指定された配列内の要素の数と同じ回数だけ指定された配列全体をチェックするため、良いことではありません...間違っている場合は修正してください。

これは私の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;
}

nが指定された配列の最大値である場合、指定された配列の2倍とn配列の1倍のみをチェックするため、これは最初のものよりも優れているはずです。nがかなり大きい場合、あまり良くないかもしれません...

さて、2つの質問：

  1. コードの効率を「測定」する方法をよく理解していますか?

  2. 特定の配列内の一意のペアの数をカウントするより良い方法はありますか?

編集：投稿したばかりで、すでに回答に圧倒されています！ありがとう！私は慎重にそれぞれを研究します.当分の間、私はHashMapに関連するものを取得していないと言います.私の知識ではまだです.

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

さて、ここにあなたの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)なります。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 
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 に答える
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 に答える
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

簡単にグループ化するために 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

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 に答える