Minimieren Sie die Anzahl ungleicher Elemente an entsprechenden Indizes zwischen den angegebenen Arrays

Vergleichen Sie die Elemente an jedem Index und passen Sie sie an, bis sie übereinstimmen, um die Anzahl inkonsistenter Elemente an entsprechenden Indizes zwischen den angegebenen Arrays zu reduzieren. Passen Sie es nach Bedarf an, während Sie gleichzeitig die Arrays durchlaufen. Die Arrays werden ähnlicher und der Anteil ungleicher Elemente nimmt dadurch ab. Durch die Verringerung ihrer Unterschiede an entsprechenden Positionen soll bei diesem Verfahren die Ähnlichkeit zwischen den Arrays erhöht werden. Das ultimative Ziel besteht darin, Arrays mit denselben Elementen an jedem Index zu erstellen, wodurch die Anzahl ungleicher Elemente verringert wird.

使用的方法

• Hashing-Ansatz

• Sortierungsansatz

哈希方法

Beim Hashing-Ansatz erstellen wir zunächst eine Hash-Tabelle für eines der Arrays, um die Anzahl ungleicher Komponenten beim Vergleich von Dateien zwischen den Arrays zu verringern. An diesem Punkt betrachten wir beim Durchlaufen des Moment-Arrays die Häufigkeit jeder Komponente in der Hash-Tabelle. Für den Fall, dass die Komponente gefunden wird, bleibt sie erhalten; Ist dies nicht der Fall, wird stattdessen die nächstgelegene koordinierende Komponente aus der Hash-Tabelle verwendet. Als Ergebnis dieses Prozesses gibt es weniger ungleiche Elemente an entsprechenden Indizes und beide Arrays werden ähnlicher. Die Effizienz dieser Methode ist von Vorteil, da sie die gewünschte Ähnlichkeit in der linearen Zeitkomplexität O(N) für durchschnittliche und beste Fälle erreichen kann.

Algorithmus

• Jedes Element des ersten Arrays sollte als Schlüssel und seine Häufigkeiten als Werte zu einer Hash-Tabelle hinzugefügt werden.

• Richten Sie einen Zeiger ein, damit Sie durch das zweite Array blättern können.

a. Bestimmen Sie, ob jedes Element im zweiten Array in der Hash-Tabelle vorhanden ist.

b. Wenn ja, lassen Sie das Element in Ruhe.

如果没有的话,找到最接近的匹配项中频率最低的哈希表元素.

d. Ändern Sie das vorhandene Element im zweiten Array in das nächstgelegene Element.

• 直到指针达到第二个数组的末尾，重复步骤3再次执行

• 由于数组的存在, 相应索引处的不相等元素数量现在将达到最低水平

• Die gewünschte Ähnlichkeit zum ersten Array ist im modifizierten zweiten Array vorhanden.

Beispiel

#include <iostream>
#include <unordered_map>
#include <vector>
#include <climits>
using namespace std;

void adjustArray(vector<int>& arr1, vector<int>& arr2) {
   unordered_map<int, int> frequency;
   for (int num : arr1) {
      frequency[num]++;
   }

   int ptr = 0;
   while (ptr < arr2.size()) {
      if (frequency.find(arr2[ptr]) != frequency.end()) {
         frequency[arr2[ptr]]--;
         if (frequency[arr2[ptr]] == 0) {
            frequency.erase(arr2[ptr]);
         }
      } else {
         int closestMatch = -1;
         int minDistance = INT_MAX; // Change minFrequency to minDistance
         for (auto it : frequency) {
            if (abs(arr2[ptr] - it.first) < minDistance) { // Change minFrequency to minDistance
               minDistance = abs(arr2[ptr] - it.first); // Change minFrequency to minDistance
               closestMatch = it.first;
            }
         }
         arr2[ptr] = closestMatch;
      }
      ptr++;
   }
}

int main() {
   vector<int> array1 = {1, 2, 3, 3, 5};
   vector<int> array2 = {5, 4, 2, 6, 7, 8};
   adjustArray(array1, array2);

   for (int num : array2) {
      cout << num << " ";
   }
   cout << endl;

   return 0;
}

输出

5 3 2 3 3 3 

Maximum Independent Set (MIS)-Ansatz

我们使用动态规划方法来寻找给定数组之间的最长公共子序列 (LCS), 以最小化对应索引处不相等元素的数量.为了跟踪两个数组中所有可能排列的元素的LCS长度,我们创建了一个二维表.为了减少差异,需要改变的元素可以通过回溯LCS来找到。通过修改LCS之外的元素以匹配LCS, 确保数组之间更高的相似度.通过优化数组以共享一个公共子序列,这种动态规划技术有效地降低了不相等元素的数量.

Algorithmus

• Setzen Sie die Längen zweier Arrays, genannt Array1 und Array2, auf m bzw. n.

• Um die LCS-Längen für alle möglichen Kombinationen von Elementen aus beiden Arrays zu speichern, erstellen Sie eine 2D-Tabelle DP der Größe (m+1) x (n+1).

• 使用两个已解决的循环来强调1和2号群集中的每个组件:

• Setze DP[i][j] = DP[i-1]. [j-1] 1, wenn die Komponenten in den aktuellen Listen gleich sind.

• Wenn die Komponenten variieren, erhöhen Sie DP[i][j] auf den höchsten möglichen Wert zwischen DP[i-1][j] und DP[i][j-1].

• Folgen Sie dem LCS rückwärts von DP[m][n] zu DP[0][0]:

• 如果array1[i-1]和array2[j-1]并将array1[i-1] 1]合并到最长公共子序列中

根据DP中哪个尊重度更高,移动到已清空的DP[i][j-1]或者向上移动到DP[i-1][j]（如果它们发生了变化）

• Elemente außerhalb des LCS in beiden Arrays müssen nach der Rückverfolgung des LCS so geändert werden, dass sie mit dem LCS übereinstimmen, um die Anzahl ungleicher Elemente zu reduzieren.

• Die Ähnlichkeit der angepassten Arrays nimmt zu und die Anzahl ungleicher Komponenten beim Vergleich von Listen nimmt ab.

Example

#include <iostream>
#include <vector>
using namespace std;

vector<int> findLCS(vector<int>& array1, vector<int>& array2) {
   return {};
}

int minimizeUnequalCount(vector<int>& array1, vector<int>& array2) {
   return 0;
}

void modifyArrays(vector<int>& array1, vector<int>& array2) {
}

int main() {
   vector<int> array1 = {1, 3, 5, 7, 9};
   vector<int> array2 = {2, 4, 5, 8, 9};

   vector<int> lcs = findLCS(array1, array2);
   cout << "Longest Common Subsequence: ";
   for (int num : lcs) {
      cout << num << " ";
   }
   cout << endl;

   int unequalCount = minimizeUnequalCount(array1, array2);
   cout << "Count of Unequal Elements after adjustment: " << unequalCount << endl;

   modifyArrays(array1, array2);
   cout << "Modified Array 1: ";
   for (int num : array1) {
      cout << num << " ";
   }
   cout << endl;

   cout << "Modified Array 2: ";
   for (int num : array2) {
      cout << num << " ";
   }
   cout << endl;

   return 0;
}

输出

Longest Common Subsequence: 
Count of Unequal Elements after adjustment: 0
Modified Array 1: 1 3 5 7 9 
Modified Array 2: 2 4 5 8 9 

Conclusion

有两种技术可用于减少两个给定数组之间对应索引处不相等元素的数量：哈希方法和排序方法。哈希方法为一个数组构建哈希表，并迭代地用哈希表中找到的最接近的匹配替换另一个数组中的元素。对于平均和最佳情况，这将实现O(N)的线性时间复杂度。另一方面，排序方法在迭代两个数组时按升序对它们进行排序，并将元素调整为较小的值。尽管它可能不总是产生最佳结果，但它使数组更具可比性。这两种方法都成功地减少了不一致元素的数量，增加了数组的相似性，并降低了对应位置的不一致元素的总数。

Das obige ist der detaillierte Inhalt vonMinimieren Sie die Anzahl ungleicher Elemente an entsprechenden Indizes zwischen den angegebenen Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!