在整数数组中找出两个元素的两对组合

Question

两对：如果有两对相同点数的骰子，玩家得分为这两个骰子点数之和。否则，玩家得分为0。例如，1、1、2、3、3放在“两对”上得8分。

示例： 1、1、2、3、3 得分8 1、1、2、3、4 得分0 1、1、2、2、2 得分6

如何高效地找到这种情况？

我一直在使用以下代码来寻找单个对子。

int max_difference = 0;
int val1 = 0 , val2 = 0;
Arrays.sort(dice);
for (int i = 0; i < dice.length - 1; i++) {
    int x = dice[i+1] - dice[i];
    if(x <= max_difference) {
        max_difference = x;
        val1 = dice[i];
        val2 = dice[i+1];

    }
}
pairScore = val1 + val2;

- Om Komawar

---

“two pairs” = 掷出2个相同点数的骰子对吗？那么如果我掷出1、1、2、3、4，结果是0吗？那1、1、1、2、2呢？还有1、1、1、1、2呢？ - Mark

@Mark，应该得到两个数字的总和，也就是6（1+1+2+2）。 - Om Komawar

不同的值是有限的。因此，可以使用桶排序或频率映射，就像@Thomas所回答的那样。 - waltersu

只是一点小提醒：如果我没记错的话，你的代码无法检测是否存在成对值，例如如果你有数值1、2、3、4、5，则x和max_difference（这个名称有些误导）的最低值将为1，你将得到一个成对分数为9（4 + 5）。 - Thomas

谢谢@Thomas，我没注意到，我会修复它的。 :) - Om Komawar

Answer 1

不需要把它搞得那么复杂，因为你只是在寻找最终的数字...

int prev = 0;
int result = 0;
int pairs = 0;

Arrays.sort(dice);
for (int i = 0; i < dice.length; i++) 
{
    int current = dice[i];
    if (current == prev) 
    {
        result += current*2;
        pairs++;
        prev = 0;
    } 
    else prev = current;
}

if (pairs == 2) return result;
else return 0;

- Mark

Answer 2

我会使用一个频率映射，即数字为键，计数器为值（因此是一个Map<Integer, Integer>）。然而，由于它用于骰子，您可以使用长度等于最大骰子值的数组进行简化（标准骰子为6）。然后检查每个数字的频率并从中获取对数。

例如：

int[] diceFrequency = new int[6];

//assuming d is in the range [1,6]
for( int d : dice ) {
  //increment the counter for the dice value
  diceFrequency[d-1]++; 
}

int numberOfPairs = 0;
int pairSum = 0;

for( int i = 0; i < diceFrequency.length; i++ ) {
  //due to integer division you get only the number of pairs, 
  //i.e. if you have 3x 1 you get 1 pair, for 5x 1 you get 2 pairs
  int num = diceFrequency[i] / 2;

  //total the number of pairs is just increases
  numberOfPairs += num; 

  //the total value of those pairs is the dice value (i+1) 
  //multiplied by the number of pairs and 2 (since it's a pair)
  pairSum += (i + 1 ) * 2 * num;
}

if( numerOfPairs >= 2 ) {
  //you have at least 2 pairs, do whatever is appropriate
}

- Thomas

---

嘿，diceFrequency[d-1]++；这是什么意思？ - Om Komawar

diceFrequency[d-1]++; 这个语句是什么意思？ - Om Komawar

//增加骰子值的计数器 - Raman Sahasi

diceFrequency[d-1]++ 会将索引为 d-1 的元素值加1。由于数组索引是从0开始的，而骰子的值是从1开始的，因此需要使用 d-1 而不是仅仅使用 d。 - Thomas

@RamanSahasi 公平地说，我在问题之后添加了注释，因为我意识到需要更多的解释。 - Thomas

Answer 3

如下所示，使用哈希映射怎么样？

public static void main(String[] args) {
    List<Integer> list = Lists.newArrayList(1, 1, 2, 3, 3, 4);
    Map<Integer, Integer> map = Maps.newHashMap();

    int result = 0;

    for (int i : list) {
        int frequency = (int) MapUtils.getObject(map, i, 0);

        if (frequency < 2) {
            map.put(i, ++frequency);
        }
    }

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() > 1) {
            result += entry.getKey() * entry.getValue();
        }
    }

    System.out.println(result);
}

- freeism

---

据我所知，这种类型的映射被称为频率映射（仅供参考 :)）。除此之外，您可以通过使用entrySet()来优化第二个循环，因为这样您就不必进行额外的查找了。 - Thomas

keySet() 被 entrySet() 替代，正如 @Thomas 所说。感谢建议。 - freeism

当你有一个豪华的牌型（例如2 2 2 3 3），你的代码会计算所有的骰子，但实际上它只应该计算两个2。 - Roland Illig

@Roland Illig 你说得很对。已按上述方式修复。谢谢 :) - freeism

Answer 4

public static void main(String[] args) {
    List<Integer> list = Lists.newArrayList(1, 1, 2, 3, 3);
    Map<Integer, Integer> map = new HashMap<>();

    int count= 0;

    for (int num : list)
        if(map.containsKey(num ))
            map.put(num , map.get(num )+1);
        else
            map.put(num , 1);

    for (int num  : map.keySet()) {
        if (map.get(num ) > 1) {
            count= count+ (num  * map.get(num ));
        }
    }

    System.out.println(count);
}

- Raman Sahasi

Answer 5

我希望能够理解这个问题。因此，我们可以使用这部分代码。

    List<Integer> diceList = new ArrayList<Integer>();
    diceList.add(1);
    diceList.add(1);
    diceList.add(2);
    diceList.add(4);
    diceList.add(3);
    diceList.add(3);
    diceList.add(6);
    diceList.add(8);

    Integer prev = null, score = 0;

    boolean flag = false;
    for (Integer val : diceList) {
        if (prev == null || !prev.equals(val)) {
            if (flag) {
                score = score + prev;
                flag = false;
            }
            prev = val;

        } else if (prev == val) {
            score = score + prev;
            flag = true;
        }
    }
    System.out.println(score);

- Mustafa YALNIZ