我只是一个初学者。我遇到了这个问题,我的代码无法满足所有/大多数测试用例。
问题:
给定一个数字数组,请找到最小和最大元素相同的非空子数组的数量。
例子:
输入:数组= [1、1、3]
输出4
解释:
所需的子数组为[1],[1],[3],[1,1]
我的解决方案:
对数组进行排序并解决问题。
代码:
for(int i = 0; i < testCases; i++){
int arraySize = in.nextInt();
int array[] = new int[arraySize];
for(int j = 0; j < arraySize; j++){
array[j] = in.nextInt();
}
temp[i] = (findSubArrays(array));
}
for(int i = 0; i < testCases; i++){
System.out.println(temp[i]);
}
private static int findSubArrays(int[] array) {
Arrays.sort(array);
//Since each element can form a sub-array of its own
int noOfSubArrays = array.length;
for(int i = 0; i < array.length-1; i++){
if(array[i] == array[i+1]){
noOfSubArrays++;
}
}
return noOfSubArrays;
}
因此,您正在对数组进行排序,以使起点和终点保持相邻,因此您不需要嵌套的遍历。那讲得通。问题在于您要计算相邻的重复项,但真正需要的是T(n)
或连续重复项的三角形数。考虑一个简单的场景:
[1, 1, 1]
您的算法返回5
,但实际上有6个子集(按开始和结束索引):
0, 0
0, 1
0, 2
1, 1
1, 2
2, 2
因此,让我们更新算法以计算每个序列的三角形数:
private static int findSubArrays(int... array) {
Arrays.sort(array);
int sequenceCount = 0;
int total = 0;
for (int i = 0; i < array.length + 1; i++) {
if (i == array.length || (i > 0 && array[i] != array[i - 1])) {
total += triangle(sequenceCount);
sequenceCount = 0;
}
sequenceCount++;
}
return total;
}
private static int triangle(int n) {
return (n * (n + 1)) / 2;
}
现在调用findSubArrays(1, 1, 1)
return6
和findSubArrays(1, 1, 3)
return 4
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句