这是我的第一篇文章，希望它符合网站的发布准则。首先，对全体社区表示感谢：从几个月的阅读中学习到很多东西：o）
前提：我是IT的大一学生。
这里是问题：我正在寻找一种有效的方法来计算给定正整数数组（这就是我所知道的）中唯一对的数量（恰好出现两次的数字），例如如果：
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;
}
我猜这应该比第一个更好，因为当n是给定数组的最大值时，它仅检查给定数组的2倍和n数组的1倍。如果n很大，可能不太好...
嗯，两个问题：
我理解的很好，如何“衡量”代码的效率？
还有一种更好的方法可以计算给定数组中唯一对的数量？
编辑：该死的我刚刚发布，我已经被答案淹没了！谢谢！我会仔细研究每个对象，暂时我说我还没有涉及到HashMap的对象：据我所知（因此再次感谢您的见解：o））
嗯，这是您的2个问题的另一个答案：
am I understanding good how to "measure" the efficiency of the code?
有多种方法可以衡量代码的效率。首先，人们区分内存效率和时间效率。计算所有这些值的通常方法是知道算法的构造块有多有效。看看wiki。
例如，使用quicksort进行分类需要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(...)为Big O notation。
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;
}
}
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);
}
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);
}
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;
您可以使用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");
}
}
一段时间后，另一个解决方案应该会很好用。
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;
}
我不知道它是否有效，但是比先对数组排序或使用哈希映射更有效。
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);
这是我尝试过的简单方法。