我對這個任務的解決方案是（我假設）時間復雜度 O(N^2)。顯然我的代碼不能很好地處理大型陣列。我怎樣才能使它更有效率？我錯過了什么？你們能推薦一些可以幫助我理解如何用 C 撰寫更高效代碼的材料嗎？謝謝！
任務：
給定一個由 N 個整陣列成的非空陣列 A。陣列 A 代表磁帶上的數字。
任何整數 P，例如 0 < P < N，都會將此磁帶分成兩個非空部分：A[0]、A[1]、...、A[P - 1] 和 A[P]、A[ P 1], ..., A[N - 1]。
兩部分的差值是：|(A[0] A[1] ... A[P - 1]) - (A[P] A[P 1] .. . A[N - 1])|
換句話說，它是第一部分的總和與第二部分的總和之間的絕對差。
例如，考慮陣列 A 使得：
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3我們可以將此磁帶拆分為四個位置：
P = 1, difference = |3 ? 10| = 7 P = 2, difference = |4 ? 9| = 5 P = 3, difference = |6 ? 7| = 1 P = 4, difference = |10 ? 3| = 7寫一個函式：
int solution(int A[], int N);即，給定一個包含 N 個整數的非空陣列 A，回傳可以實作的最小差異。
例如，給定：
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3如上所述，該函式應回傳 1。
為以下假設撰寫一個有效的演算法：
- N 是 [2..100,000] 范圍內的整數；
- 陣列 A 的每個元素都是 [?1,000..1,000] 范圍內的整數。
我的解決方案：
#include <stdint.h>
#include <stdlib.h>
int solution(int A[], int N) {
uint32_t p = 1, i=0;
int64_t lowestSum = 0, sum1 = 0, sum2 = 0, sum = 0;
{
// iterate over all possible values of P
for(p=1; p<N; p )
{
sum1 = 0;
sum2 = 0;
for(i=0; i<N; i )
{
if(i<p)
{
sum1 = A[i];
}
else
{
sum2 = A[i];
}
}
sum = abs(sum1 - sum2);
//if this is the first iteration,
//initialize the lowest sum with current sum
if(p==1)
{
lowestSum = sum;
}
else if(lowestSum > sum)
{
lowestSum = sum;
}
}
}
return lowestSum;
}
uj5u.com熱心網友回復：
根據 Weather Vane 和 Jonathan Leffler 提供的建議，我能夠想出這個解決方案，得到 100% 的結果。吸取的教訓是不惜一切代價簡單地嘗試避免 O(N^2) 解決方案。我希望我能訓練自己的思維（更快）看到這些解決方案。
#include <stdint.h>
#include <stdlib.h>
int solution(int A[], int N) {
int64_t LeftRight[N], sum = 0;
int64_t lowest_diff = 0, diff = 0;
uint32_t i = 0;
for(i=0; i<N; i )
{
sum = A[i];
LeftRight[i] = sum;
}
sum = 0;
i = N - 1;
while(i > 0)
{
sum = A[i];
diff = abs(LeftRight[i-1]-sum);
//is this first elemnt on the right?
if(i == (N-1))
{
lowest_diff = diff;
}
else if(lowest_diff > diff)
{
lowest_diff = diff;
}
i--;
}
return lowest_diff;
}
uj5u.com熱心網友回復：
資料約束表明輸入的最大總和是100000 * 1000 = 100000000可以適合 32 位的int。
我建議，如果資料來自流，您只需要在第一遍中存盤值的運行總和，然后在第二遍中找出答案。
這是O(N)。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
int n = 0;
int sum = 0;
scanf("%d", &n);
int *left = malloc(n * sizeof *left);
for(int i = 0; i < n; i ) {
int val;
scanf("%d", &val);
sum = val;
left[i] = sum;
}
int mindiff = INT_MAX;
for(int i = 0; i < n; i ) {
int right = sum - left[i];
int diff = abs(left[i] - right);
if(diff < mindiff) {
mindiff = diff;
}
}
printf("mindiff = %d\n", mindiff);
free(left);
return 0;
}
對于指定的輸入
5
3 1 2 4 3
輸出是
mindiff = 1
我意識到該程式沒有任何錯誤檢查，這不是很好，但它確實顯示了演算法。
uj5u.com熱心網友回復：
這是我開發的一些相當花哨的代碼，但核心演算法使用 O(1) 空間和 O(N) 時間進行分析，只對資料進行 2 次傳遞。
該程式采用可選-v引數來列印對其作業的詳細分析。它使用了我的正常錯誤處理代碼這是我可以SOQ（堆疊溢位問題）庫在GitHub上的檔案stderr.c，并stderr.h在SRC / libsoq子目錄。我發現它使錯誤處理變得更加容易，所以我更傾向于實際進行必要的錯誤檢查。它檢查輸入是否滿足條件并在資料無效時報告錯誤（并退出）。它調整詳細資料的詳細布局以保持列對齊。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "stderr.h"
static const char optstr[] = "vh";
static const char usestr[] = "[-vh]";
static const char hlpstr[] =
" -h Print this help message and exit\n"
" -v Print details of calculation as it is done\n"
;
static int solution(int A[], int N);
static int vflag = 0;
static int n_width = 0;
static int s_width = 0;
int main(int argc, char **argv)
{
err_setarg0(argv[0]);
int opt;
while ((opt = getopt(argc, argv, optstr)) != -1)
{
switch (opt)
{
case 'v':
vflag = 1;
break;
case 'h':
err_help(usestr, hlpstr);
/*NOTREACHED*/
default:
err_usage(usestr);
/*NOTREACHED*/
}
}
if (optind != argc)
err_usage(usestr);
int N;
if (scanf("%d", &N) != 1)
err_error("failed to read array size\n");
if (N < 2 || N > 100000)
err_error("array size %d out of range 2..100,000\n", N);
/* VLA - but size was checked and won't overflow stack */
int array[N];
for (int i = 0; i < N; i )
{
if (scanf("%d", &array[i]) != 1)
err_error("failed to read element %d of array\n", i);
if (array[i] < -1000 || array[i] > 1000)
err_error("element %d (%d) is out of range -1000.. 1000\n", i, array[i]);
}
n_width = snprintf(0, 0, "%d", N - 1);
s_width = snprintf(0, 0, "%d", (N - 1) * -1000);
int result = solution(array, N);
printf("result: %d\n", result);
return 0;
}
static inline int abs_diff(int a, int b)
{
return abs(a - b);
}
static int solution(int A[], int N)
{
int total = 0;
/* First pass over array - O(N) */
for (int i = 0; i < N; i )
total = A[i];
if (vflag)
printf("N = %d; total = %d\n", N, total);
/* Second pass over array - O(N) */
int lhs = A[0];
int min_gap = abs_diff(lhs, total - lhs);
if (vflag)
{
printf("A[%*d] = ]: lhs = %*d, rhs = %*d, |lhs - rhs| = %*d ** minimum so far\n",
n_width, 0, A[0], s_width, lhs, s_width, total - lhs,
s_width, abs_diff(lhs, total - lhs));
}
for (int i = 1; i < N; i )
{
lhs = A[i];
int diff = abs_diff(lhs, total - lhs);
if (vflag)
{
const char *marker = (diff < min_gap) ? " ** minimum so far" : "";
printf("A[%*d] = ]: lhs = %*d, rhs = %*d, |lhs - rhs| = %*d%s\n",
n_width, i, A[i], s_width, lhs, s_width, total - lhs,
s_width, abs_diff(lhs, total - lhs), marker);
}
if (diff < min_gap)
min_gap = diff;
}
return min_gap;
}
對于問題中的樣本資料，詳細輸出為：
N = 5; total = 13
A[0] = 3: lhs = 3, rhs = 10, |lhs - rhs| = 7 ** minimum so far
A[1] = 1: lhs = 4, rhs = 9, |lhs - rhs| = 5 ** minimum so far
A[2] = 2: lhs = 6, rhs = 7, |lhs - rhs| = 1 ** minimum so far
A[3] = 4: lhs = 10, rhs = 3, |lhs - rhs| = 7
A[4] = 3: lhs = 13, rhs = 0, |lhs - rhs| = 13
result: 1
請注意，輸出比問題中的分析顯示的多一行。
對于 20 行隨機輸入，我得到：
N = 20; total = 973
A[ 0] = -360: lhs = -360, rhs = 1333, |lhs - rhs| = 1693 ** minimum so far
A[ 1] = -675: lhs = -1035, rhs = 2008, |lhs - rhs| = 3043
A[ 2] = 245: lhs = -790, rhs = 1763, |lhs - rhs| = 2553
A[ 3] = 47: lhs = -743, rhs = 1716, |lhs - rhs| = 2459
A[ 4] = -100: lhs = -843, rhs = 1816, |lhs - rhs| = 2659
A[ 5] = 987: lhs = 144, rhs = 829, |lhs - rhs| = 685 ** minimum so far
A[ 6] = 16: lhs = 160, rhs = 813, |lhs - rhs| = 653 ** minimum so far
A[ 7] = -146: lhs = 14, rhs = 959, |lhs - rhs| = 945
A[ 8] = 126: lhs = 140, rhs = 833, |lhs - rhs| = 693
A[ 9] = -541: lhs = -401, rhs = 1374, |lhs - rhs| = 1775
A[10] = -116: lhs = -517, rhs = 1490, |lhs - rhs| = 2007
A[11] = 842: lhs = 325, rhs = 648, |lhs - rhs| = 323 ** minimum so far
A[12] = -769: lhs = -444, rhs = 1417, |lhs - rhs| = 1861
A[13] = -361: lhs = -805, rhs = 1778, |lhs - rhs| = 2583
A[14] = 295: lhs = -510, rhs = 1483, |lhs - rhs| = 1993
A[15] = -471: lhs = -981, rhs = 1954, |lhs - rhs| = 2935
A[16] = 398: lhs = -583, rhs = 1556, |lhs - rhs| = 2139
A[17] = 932: lhs = 349, rhs = 624, |lhs - rhs| = 275 ** minimum so far
A[18] = 270: lhs = 619, rhs = 354, |lhs - rhs| = 265 ** minimum so far
A[19] = 354: lhs = 973, rhs = 0, |lhs - rhs| = 973
result: 265
對于完整的 100,000 行輸入，輸出開始和結束如下：
N = 100000; total = -53534
A[ 0] = -301: lhs = -301, rhs = -53233, |lhs - rhs| = 52932 ** minimum so far
A[ 1] = 338: lhs = 37, rhs = -53571, |lhs - rhs| = 53608
A[ 2] = -35: lhs = 2, rhs = -53536, |lhs - rhs| = 53538
A[ 3] = 243: lhs = 245, rhs = -53779, |lhs - rhs| = 54024
A[ 4] = -537: lhs = -292, rhs = -53242, |lhs - rhs| = 52950
A[ 5] = 687: lhs = 395, rhs = -53929, |lhs - rhs| = 54324
A[ 6] = 116: lhs = 511, rhs = -54045, |lhs - rhs| = 54556
A[ 7] = -257: lhs = 254, rhs = -53788, |lhs - rhs| = 54042
A[ 8] = 288: lhs = 542, rhs = -54076, |lhs - rhs| = 54618
A[ 9] = 592: lhs = 1134, rhs = -54668, |lhs - rhs| = 55802
A[ 10] = -385: lhs = 749, rhs = -54283, |lhs - rhs| = 55032
A[ 11] = -254: lhs = 495, rhs = -54029, |lhs - rhs| = 54524
A[ 12] = 816: lhs = 1311, rhs = -54845, |lhs - rhs| = 56156
A[ 13] = -946: lhs = 365, rhs = -53899, |lhs - rhs| = 54264
A[ 14] = -477: lhs = -112, rhs = -53422, |lhs - rhs| = 53310
A[ 15] = -61: lhs = -173, rhs = -53361, |lhs - rhs| = 53188
A[ 16] = 225: lhs = 52, rhs = -53586, |lhs - rhs| = 53638
A[ 17] = 174: lhs = 226, rhs = -53760, |lhs - rhs| = 53986
A[ 18] = -269: lhs = -43, rhs = -53491, |lhs - rhs| = 53448
A[ 19] = -408: lhs = -451, rhs = -53083, |lhs - rhs| = 52632 ** minimum so far
A[ 20] = 123: lhs = -328, rhs = -53206, |lhs - rhs| = 52878
A[ 21] = 124: lhs = -204, rhs = -53330, |lhs - rhs| = 53126
A[ 22] = -364: lhs = -568, rhs = -52966, |lhs - rhs| = 52398 ** minimum so far
A[ 23] = 41: lhs = -527, rhs = -53007, |lhs - rhs| = 52480
A[ 24] = -617: lhs = -1144, rhs = -52390, |lhs - rhs| = 51246 ** minimum so far
A[ 25] = 583: lhs = -561, rhs = -52973, |lhs - rhs| = 52412
A[ 26] = -860: lhs = -1421, rhs = -52113, |lhs - rhs| = 50692 ** minimum so far
A[ 27] = 39: lhs = -1382, rhs = -52152, |lhs - rhs| = 50770
A[ 28] = 465: lhs = -917, rhs = -52617, |lhs - rhs| = 51700
A[ 29] = -413: lhs = -1330, rhs = -52204, |lhs - rhs| = 50874
A[ 30] = -530: lhs = -1860, rhs = -51674, |lhs - rhs| = 49814 ** minimum so far
…
A[18048] = 381: lhs = -27278, rhs = -26256, |lhs - rhs| = 1022
A[18049] = 510: lhs = -26768, rhs = -26766, |lhs - rhs| = 2 ** minimum so far
A[18050] = -754: lhs = -27522, rhs = -26012, |lhs - rhs| = 1510
…
A[99990] = -196: lhs = -57461, rhs = 3927, |lhs - rhs| = 61388
A[99991] = 698: lhs = -56763, rhs = 3229, |lhs - rhs| = 59992
A[99992] = -141: lhs = -56904, rhs = 3370, |lhs - rhs| = 60274
A[99993] = 907: lhs = -55997, rhs = 2463, |lhs - rhs| = 58460
A[99994] = 158: lhs = -55839, rhs = 2305, |lhs - rhs| = 58144
A[99995] = 563: lhs = -55276, rhs = 1742, |lhs - rhs| = 57018
A[99996] = 851: lhs = -54425, rhs = 891, |lhs - rhs| = 55316
A[99997] = -12: lhs = -54437, rhs = 903, |lhs - rhs| = 55340
A[99998] = 703: lhs = -53734, rhs = 200, |lhs - rhs| = 53934
A[99999] = 200: lhs = -53534, rhs = 0, |lhs - rhs| = 53534
result: 2
我有一個方便的亂數生成器程式，可以告訴它生成介于 -1000 和 1000 之間的 N 個整數（還有更多，但這就是該測驗所必需的全部）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/406064.html
標籤：
上一篇：嘗試反轉字串會導致空白字串