我已经解决了hackerrank的Sock Merchant问题,但是我想要减少代码复杂度(我不确定是否可能)。
John在一家服装店工作。他有很多袜子要按颜色配对销售。给定一个表示每只袜子颜色的整数数组,确定有多少双颜色相同的袜子。
例如,有n=7只颜色为ar=[1,2,1,2,1,3,2]的袜子。有1双颜色为1的袜子和1双颜色为2的袜子。还剩下3只单独的袜子,每种颜色各1只。一共有2双袜子。
函数说明
请完成下面编辑器中的sockMerchant函数。它必须返回一个整数,表示可用的匹配袜子对数。
sockMerchant具有以下参数:
n:堆叠中袜子的数量
ar:每只袜子的颜色
输入格式
第一行包含一个整数n,表示在ar中表示的袜子数量。 第二行包含n个以空格分隔的整数,描述堆叠中袜子的颜色ar[i]。
约束条件
1 <= n <= 100
1 <= ar[i] <= 100 其中 0 <= i < n
输出格式
返回John可以出售的一共有多少双匹配的袜子。
示例输入
9
10 20 20 10 10 30 50 10 20
样例输出
3
我的解决方案:
package com.hackerrank.test;
public class Solution {
public static void main(String[] args) {
//Initialize array
int[] arr = new int[]{10, 20, 20, 10, 10, 30, 50, 10, 20};
//Array fr will store frequencies of element
System.out.println("---------------------------------------");
System.out.println(" sockMerchant output " + sockMerchant(9, arr));
System.out.println("---------------------------------------");
}
static int sockMerchant(int n, int[] ar) {
int pairs = 0;
int frequencyArray[] = new int[ar.length];
int frequencyTemp = -1;
for (int i = 0; i < ar.length; i++) {
int count = 1;
for (int j = i + 1; j < ar.length; j++) {
if (ar[i] == ar[j]) {
count++;
frequencyArray[j] = frequencyTemp;
}
}
if (frequencyArray[i] != frequencyTemp) {
frequencyArray[i] = count;
}
}
for (int i = 0; i < frequencyArray.length; i++) {
if (frequencyArray[i] != frequencyTemp) {
int divide = frequencyArray[i] / 2;
pairs += divide;
}
}
return pairs;
}
}
输出结果为:
---------------------------------------
sockMerchant frequency 3
---------------------------------------