C 程序找到要删除的子数组的起始索引和结束索引,以使给定数组的左侧和右侧总和相等。如果它不可能打印-1。我需要它适用于任何阵列,这只是为了测试。这是找到平衡的代码。
#include <stdio.h>
int equilibrium(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
/* Check for indexes one by one until
an equilibrium index is found */
for (i = 0; i < n; ++i) {
/* get left sum */
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];
/* get right sum */
rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
/* if leftsum and rightsum are same,
then we are done */
if (leftsum == rightsum)
return i;
}
/* return -1 if no equilibrium index is found */
return -1;
}
// Driver code
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("%d", equilibrium(arr, arr_size));
getchar();
return 0;
}
最佳答案
您可以在O(NlogN)
或O(N)
(平均情况下)中解决此问题。
首先,你需要做一个预处理,将所有的和从右到左保存在一个数据结构中,特别是一个平衡的二叉搜索树(例如 Red Black tree ,AVL Tree,Splay Tree 等,如果你可以的话使用 stdlib
,只需使用 std::multiset
) 或 HashTable (在 stdlib
中是 std::unordered_multiset
):
void preProcessing(dataStructure & ds, int * arr, int n){
int sum = 0;
int * toDelete = (int) malloc(n)
for(int i = n-1; i >= 0; --i){
sum += arr[i];
toDelete[i] = sum; // Save items to delete later.
tree.insert(sum);
}
所以要解决这个问题你只需要遍历一次数组:
// It considers that the deleted subarray could be empty
bool Solve(dataStructure & ds, int * arr, int n, int * toDelete){
int sum = 0;
bool solved = false; // true if a solution is found
for(int i = 0 ; i < n; ++i){
ds.erase(toDelete[i]); // deletes the actual sum up to i-th element from data structure, as it couldn't be part of the solution.
// It costs O(logN)(BBST) or O(1)(Hashtable)
sum += arr[i];
if(ds.find(sum)){// If sum is in ds, then there's a leftsum == rightsum
// It costs O(logN)(BBST) or O(1)(HashTable)
solved = true;
break;
}
}
return solved;
}
然后,如果您使用 BBST(平衡二叉搜索树),您的解决方案将是 O(NlogN)
,但是,如果您使用 HashTable,您的解决方案将是 O(N)
平均。我不会实现它,所以可能存在错误,但我会尝试解释主要思想。
关于c - 通过删除子数组使数组左右两边的和相等,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53900626/