java 在 int 数组中计算唯一对的有效方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14748688/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficient way to count unique pairs in int array
提问by Goet
This is my first post, hope it complies with posting guidelines of the site. First of all a generic thanks to all the community: reading you from some months and learned a lot :o)
这是我的第一篇文章，希望它符合网站的发布指南。首先，感谢所有社区：从几个月的时间里读到你并学到了很多：o）
Premise: I'm a first years student of IT.
前提：我是 IT 专业的一年级学生。
Here's the question: I'm looking for an efficient way to count the number of unique pairs (numbers that appear exactly twice) in a given positive int array (that's all I know), e.g. if:
问题是：我正在寻找一种有效的方法来计算给定正整数数组中唯一对（恰好出现两次的数字）的数量（这就是我所知道的），例如，如果：
int[] arr = {1,4,7,1,5,7,4,1,5};
the number of unique pairs in arr is 3 (4,5,7).
arr 中唯一对的数量是 3 (4,5,7)。
I have some difficulties in... evaluating the efficiency of my proposals let's say.
我在……评估我的提案的效率方面遇到了一些困难，比如说。
Here's the first code I did:
这是我做的第一个代码：
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;
}
This shoudn't be good cause it checks the whole given array as many times as the number of elements in the given array... correct me if I'm wrong.
这应该不好，因为它检查整个给定数组的次数与给定数组中的元素数一样多……如果我错了，请纠正我。
This is my second code:
这是我的第二个代码：
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;
}
I guess this should be better than the first one since it checks only 2 times the given array and 1 time the n array, when n is the max value of the given array. May be not so good if n is quite big I guess...
我想这应该比第一个更好，因为当 n 是给定数组的最大值时，它只检查给定数组的 2 次和 n 数组的 1 次。如果 n 很大，我猜可能不是那么好......
Well, 2 questions:
嗯，2个问题：
am I understanding good how to "measure" the efficiency of the code?
there's a better way to count the number of unique pairs in a given array?
我是否理解如何“衡量”代码的效率？
有更好的方法来计算给定数组中唯一对的数量吗？
EDIT: Damn I've just posted and I'm already swamped by answers! Thanks! I'll study each one with care, for the time being I say I don't get those involving HashMap: out of my knowledge yet (hence thanks again for the insight:o) )
编辑：该死的，我刚刚发布了，我已经被答案淹没了！谢谢！我会仔细研究每一个，暂时我说我没有得到那些涉及 HashMap 的：我的知识之外（因此再次感谢您的洞察力：o））
回答by Achintya Jha
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);
}
回答by Ostap Andrusiv
Well, here's another answer to your's 2 questions:
好吧，这是您的两个问题的另一个答案：
am I understanding good how to "measure" the efficiency of the code?
There are various ways to measure efficiency of the code. First of all, people distinguish between memory efficiencyand time efficiency. The usual way to count all these values is to know, how efficient are the building blocks of your algorithm. Have a look at the wiki.
有多种方法可以衡量代码的效率。首先，人们区分内存效率和时间效率。计算所有这些值的常用方法是了解算法的构建块的效率。看看维基。
For instance, sorting using quicksort would need n*log(n)operations. Iterating through the array would need just noperations, where nis number of elements in the input.
例如，使用快速排序进行排序需要n*log(n)操作。遍历数组只需要n操作，其中n是输入中的元素数。
there's a better way to count the number of unique pairs in a given array?
Here's another solution for you. The complixity of this one would be: O(n*log(n)+n), where O(...)is Big O notation.
这是为您提供的另一种解决方案。这一个的复杂性是：O(n*log(n)+n)，哪里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;
}
}
回答by Mikhail Vladimirov
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;
回答by Kevin Bowersox
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);
}
回答by goravine
you can use HashMap for easy grouping. here is my code.
您可以使用 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");
}
added for checking the unique pair, you can delete the print out one
添加用于检查唯一对，您可以删除打印出来的
//unique pair
for(int key:asd.keySet())
{
if(asd.get(key) == 2)
{
System.out.println(key+" are a unique pair");
}
}
回答by duffy356
after some time another solution, which should work great.
一段时间后，另一个解决方案应该很好用。
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;
}
i am not shure if it works, but it is more effective than sorting the array first, or using hashmaps....
我不确定它是否有效，但它比先对数组进行排序或使用哈希图更有效....
