แนวคิดง่ายๆ เกี่ยวกับอัลกอริธึม "การหาคู่ของตัวเลขทั้งหมดในอาร์เรย์ที่ผลรวมเป็นจำนวนคงที่"

ผู้เขียน：Eve Cole เวลาอัปเดต：2010-01-21 16:42:05

1. คำอธิบายหัวข้อ

มีอาร์เรย์ a[1000] ซึ่งเก็บจำนวนเต็ม 1,000 ตัว โปรดค้นหาคู่ตัวเลขทั้งหมดในอาร์เรย์ที่มีผลรวมเป็น M ตัวอย่างเช่น อาร์เรย์คือ -1,2,4,6,5,3,4,2,9,0,8,3 จากนั้นคู่ตัวเลขที่ผลรวมคือ 8 คือ (-1,9), (2, 6), ( 4,4), (5,3), (5,3), (0,8)

2. อัลกอริธึมที่พบบ่อยที่สุด

ในกรณีของความซับซ้อนที่ลดไม่ได้ อัลกอริธึมที่ง่ายที่สุดสำหรับปัญหานี้จะเป็นดังนี้:

รายการคงที่ส่วนตัว <int[]> UseNormalWay (int [] arr, int sumTotal)
-
รายการ<int[]>ผลลัพธ์ = รายการใหม่<int[]>();

สำหรับ (int i = 0; i < arr.Length; i++)
-
int waitNum = sumTotal - arr [i];

สำหรับ (int j = i + 1; j < arr.Length; j++)
-
ถ้า (arr[j] ==expectNum)
-
result.Add(ใหม่ int[]{arr[i],expectNum});
-
-
-

ส่งคืนผลลัพธ์;
-
ใช้การวนซ้ำสองระดับเพื่อค้นหาคู่ทั้งหมดที่มีผลรวมเป็นตัวเลขคงที่ sumTotal และจัดเก็บคู่ที่พบไว้ในรายการ อย่างไรก็ตาม ความซับซ้อนของอัลกอริธึมนี้ค่อนข้างสูง และจริงๆ แล้วอัลกอริธึมจะทำงานซ้ำๆ บ้างระหว่างการแวะผ่าน:

1) ไม่จำเป็นต้องประมวลผลลำดับที่จับคู่ไว้ก่อนหน้านี้ในลูปถัดไป

2) เมื่อค้นหาตัวเลขที่มีผลรวมเป็น sumTotal ควรมีกระบวนการบางอย่างที่สามารถใช้ร่วมกันได้

จากสองประเด็นนี้ คุณสามารถอ้างอิงแนวคิดแบ็คแพ็ค 01 หรือแนวคิดการเขียนโปรแกรมแบบไดนามิกได้ (บางทีอาจไม่เหมาะสม ฉันมีความเข้าใจอย่างผิวเผินเกี่ยวกับแนวคิดทั้งสองนี้) เพื่อปรับปรุงอัลกอริธึมนี้และใช้การเรียกซ้ำเพื่อดำเนินการ

2. ใช้อัลกอริธึมแบบเรียกซ้ำ

รหัสที่ใช้อัลกอริธึมแบบเรียกซ้ำมีดังนี้:

รายการคงที่ส่วนตัว <int[]> UseRecursion (int [] arr, ความยาว int, int sumTotal)
-
รายการ<int[]>ผลลัพธ์ = รายการใหม่<int[]>();
int[] nextArr = int ใหม่ [ความยาว];
int ถัดไปความยาว = 0;
int waitNum = ผลรวม - arr [0];
int findStartNumCount = 0;
int findEndNumCount = 0;

สำหรับ (int i = 1; i <ความยาว; i++)
-
ถ้า (arr[i] ==expectNum)
-
int CircleCount = arr[0] == expenNum ? findEndNumCount : findStartNumCount;
วงกลมนับ += 1;

สำหรับ (int j = 0; j <circleCount; j++)
-
ผลลัพธ์เพิ่ม (int ใหม่ [] { arr [0],expectNum });
-

ค้นหาEndNumCount++;
-
อย่างอื่นถ้า (arr[i] == arr[0])
-
สำหรับ (int j = 0; j < findEndNumCount; j++)
-
ผลลัพธ์เพิ่ม (int ใหม่ [] { ExpectNum, arr [0] });
-
ค้นหาStartNumCount++;
-
อื่น
-
nextArr[nextLength++] = arr[i];
-
-

ถ้า (ความยาวถัดไป > 0)
-
รายการ <int[]> nextResult = UseRecursion (nextArr, nextLength, sumTotal);
foreach (รายการ int[] ในผลลัพธ์ถัดไป)
-
result.Add(รายการ);
-
-

ส่งคืนผลลัพธ์;
-
หลังจากการเรียกซ้ำแต่ละครั้ง ตัวเลขทั้งหมดที่ยังไม่ได้ตรวจสอบการจับคู่จะถูกสร้างเป็นอาเรย์ใหม่เพื่อประมวลผลในการเรียกซ้ำครั้งถัดไป แต่จะทำให้เปลืองพื้นที่จำนวนมาก โดยเฉพาะเมื่ออาเรย์มีขนาดใหญ่ก็จะกินหน่วยความจำจำนวนมาก . เพื่อไม่ให้สร้างอาร์เรย์ใหม่ซ้ำๆ ทุกครั้ง คุณสามารถประมวลผลอาร์เรย์เดิม ลบหมายเลขที่ตรงกันออกจากอาร์เรย์ และย้ายหมายเลขถัดไปไปข้างหน้าเพื่อแทนที่

3. อัลกอริธึมการเปลี่ยนแปลงแบบไดนามิกของอาร์เรย์

รหัสสำหรับอัลกอริทึมนี้เป็นดังนี้:

รายการคงที่ส่วนตัว <int[]> UseAdvancedWay (int [] arr, int sumTotal)
-
รายการ<int[]>ผลลัพธ์ = รายการใหม่<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;

ในขณะที่ (startIndex < endIndex)
-
int waitNum = sumTotal - arr [startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;

สำหรับ (int i = startIndex + 1; i <= endIndex; i++)
-
ถ้า (findStartNumCount > 0 || findEndNumCount > 0)
-
arr[i] = arr[i + findStartNumCount + findEndNumCount];
-

ถ้า (arr[i] ==expectNum)
-
int CircleCount = arr[startIndex] == waitNum ? findEndNumCount : findStartNumCount;
วงกลมนับ += 1;

สำหรับ (int iStart = 0; iStart <circleCount; iStart++)
-
ผลลัพธ์เพิ่ม (int ใหม่ [] { arr [startIndex], arr [i] });
-

ค้นหาEndNumCount++;
endIndex--;
ฉัน--;
-
อย่างอื่นถ้า (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
-
สำหรับ (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
-
ผลลัพธ์ เพิ่ม (int ใหม่ [] { ExpectNum, arr [i] });
-

ค้นหาStartNumCount++;
endIndex--;
ฉัน--;
-
-
เริ่มต้นดัชนี++;
-

ส่งคืนผลลัพธ์;
-

อัลกอริธึมนี้จะทำลายข้อมูลของอาเรย์ดั้งเดิม

4. การเปรียบเทียบเวลาของอัลกอริธึมทั้งสาม

แม้ว่าความตั้งใจเดิมของอัลกอริธึมสองตัวหลังคือการลดความซับซ้อนของเวลา แต่ก็ไม่ได้ดีไปกว่าอัลกอริธึมแรกในการทดสอบเฉพาะเจาะจงมากนัก โดยเฉพาะอย่างยิ่ง อัลกอริธึมแบบเรียกซ้ำจะใช้เวลานานกว่าอัลกอริธึมแรกอย่างมาก อาจมีปัญหาพื้นฐานกับความคิดของฉัน หรือตัวอย่างนี้อาจง่ายเกินไปและทำให้เวลาที่ใช้ข้อมูลมือถือชัดเจน

ฉันไม่เคยค้นคว้าเกี่ยวกับอัลกอริทึมมากนัก ฉันหวังว่าผู้เชี่ยวชาญจะสามารถให้คำแนะนำฉันได้ ฉันเชื่อว่าจะต้องมีวิธีแก้ปัญหาที่สมบูรณ์แบบกว่านี้

5. รหัสทั้งหมด

โมฆะคงที่หลัก (สตริง [] args)
-
ค่าคงที่ NUM_COUNT = 8000;
ค่าคงที่ MIN_NUM = -4;
ค่าคงที่ MAX_NUM = 12;
const int รวม = 8;

int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);

//Console.WriteLine("ตัวเลขที่สร้างขึ้นคือ:n---------------------------------------- ---- -");
//PrintNumArray(arr);

//วิธีปกติ
ช่วงเวลา NormalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
นาฬิกาจับเวลา NormalStw = นาฬิกาจับเวลาใหม่ ();
ปกติStw.Start();

รายการ <int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);

สองเท่า ปกติCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
ปกติStw.Stop();
สองเท่าของ realTime ปกติ = NormalStw.Elapsed.TotalMilliseconds;

// พิมพ์ผลลัพธ์ปกติ
//Console.WriteLine("คู่ผลลัพธ์ของหมายเลขด้วยวิธีปกติคือ:n-------------------------------- --");
//PrintNumPairs(ผลลัพธ์ใช้วิธีปกติ);

// วิธีการเรียกซ้ำ
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
นาฬิกาจับเวลา recuStw = นาฬิกาจับเวลาใหม่ ();
recuStw.Start();

รายการ<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);

recuCupTime สองเท่า = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliseconds;
recuStw.Stop();
recuRealTime สองเท่า = recuStw.Elapsed.TotalMilliseconds;

// พิมพ์ผลลัพธ์การเรียกซ้ำ
//Console.WriteLine("คู่ผลลัพธ์ของตัวเลขที่ใช้วิธีเรียกกลับคือ:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);

// วิธีขั้นสูง
ช่วงเวลา advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
นาฬิกาจับเวลา advStw = นาฬิกาจับเวลาใหม่ ();
advStw.Start();

รายการ <int[]> resultUseAdvancedWay = UseAdvancedWay (arr, TOTAL);

advCupTime สองเท่า = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.หยุด();
advRealTime สองเท่า = advStw.Elapsed.TotalMilliseconds;

// พิมพ์ผลลัพธ์ขั้นสูง
//Console.WriteLine("คู่หมายเลขผลลัพธ์โดยใช้วิธีขั้นสูงคือ:n-------------------------------- --");
//PrintNumPairs(ผลลัพธ์ใช้ขั้นสูง);

Console.WriteLine("n================================nเวลาที่ใช้:n---- ----------------------------------");
Console.WriteLine(String.Format("ปกติ : นับ - {0} เวลา Cpu - {1} เรียลไทม์ - {2}", resultUseNormalWay.Count, NormalCupTime, NormalRealTime));
Console.WriteLine(String.Format("การเรียกซ้ำ: นับ - {0} เวลา Cpu - {1} เรียลไทม์ - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("ขั้นสูง : นับ - {0} เวลา Cpu - {1} เรียลไทม์ - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));

คอนโซล.อ่าน();
-

int คงที่ส่วนตัว [] GenerateArray (int numCount, int minValue, int maxValue)
-
int[] arr = int ใหม่[numCount];

สุ่ม rdm = สุ่มใหม่ ((int) DateTime.Now.Ticks);
สำหรับ (int i = 0; i < arr.Length; i++)
-
arr[i] = rdm.ถัดไป(minValue, maxValue);
-

กลับถึง;
-

โมฆะคงที่ส่วนตัว PrintNumArray (int [] arr)
-
สำหรับ (int i = 0; i < arr.Length; i++)
-
ถ้า (i > 0 && ฉัน % 20 == 0)
-
Console.Write("n");
-
Console.Write(String.Format("{0,2} ", arr[i]));
-
Console.Write("n");
-

โมฆะคงที่ส่วนตัว PrintNumPairs (รายการ <int []> numList)
-
สำหรับ (int i = 0; i < numList.Count; i++)
-
ถ้า (i > 0 && ฉัน % 10 == 0)
-
Console.Write("n");
-
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
-
Console.Write("n");
-

รายการคงที่ส่วนตัว <int[]> UseNormalWay (int [] arr, int sumTotal)
-
รายการ<int[]>ผลลัพธ์ = รายการใหม่<int[]>();

สำหรับ (int i = 0; i < arr.Length; i++)
-
int waitNum = sumTotal - arr [i];

สำหรับ (int j = i + 1; j < arr.Length; j++)
-
ถ้า (arr[j] ==expectNum)
-
result.Add(ใหม่ int[]{arr[i],expectNum});
-
-
-

ส่งคืนผลลัพธ์;
-

สำหรับ (int j = 0; j <circleCount; j++)
-
ผลลัพธ์เพิ่ม (int ใหม่ [] { arr [0],expectNum });
-

ค้นหาEndNumCount++;
-
อย่างอื่นถ้า (arr[i] == arr[0])
-
สำหรับ (int j = 0; j < findEndNumCount; j++)
-
ผลลัพธ์ เพิ่ม (int ใหม่ [] { ExpectNum, arr [0] });
-
ค้นหาStartNumCount++;
-
อื่น
-
nextArr[nextLength++] = arr[i];
-
-

ส่งคืนผลลัพธ์;
-

ในขณะที่ (startIndex < endIndex)
-
int waitNum = sumTotal - arr [startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;

สำหรับ (int i = startIndex + 1; i <= endIndex; i++)
-
ถ้า (findStartNumCount > 0 || findEndNumCount > 0)
-
arr[i] = arr[i + findStartNumCount + findEndNumCount];
-

ถ้า (arr[i] ==expectNum)
-
int CircleCount = arr[startIndex] == waitNum ? findEndNumCount : findStartNumCount;
วงกลมนับ += 1;

สำหรับ (int iStart = 0; iStart <circleCount; iStart++)
-
ผลลัพธ์เพิ่ม (int ใหม่ [] { arr [startIndex], arr [i] });
-

ค้นหาStartNumCount++;
endIndex--;
ฉัน--;
-
-
เริ่มต้นดัชนี++;
-

ส่งคืนผลลัพธ์;
-