Wie finde ich mit C# alle eindeutigen Quadrupel nahe Null?

Der einfachste Weg besteht darin, dass wir vier verschachtelte Schleifen erstellen und nacheinander prüfen können, ob die Summe aller vier Elemente Null ist. Wenn die Summe der vier Elemente Null ist, drucken Sie die Elemente aus.

Zeitkomplexität - O(n⁴)

- O(1)

Wir können eine ungeordnete Mengendatenstruktur verwenden, um jeden Wert des Arrays zu speichern. Set bietet den Vorteil, dass die Suche nach Elementen in O(1)-Zeit erfolgt. Wir suchen also für jedes Paar im Array nach dem negativen Wert seiner Summe, der möglicherweise in der Menge vorhanden ist. Wenn ein solches Element gefunden wird, können wir ein Tripel drucken, das aus einem Paar ganzer Zahlen und dem negativen Wert ihrer Summe besteht.

Zeitkomplexität - O(n ³)

Raumkomplexität - O(n)

Beispiel

public class Arrays{
   public List<List<int>> FourSum(int[] nums){
      List<List<int>> res = new List<List<int>>();
      if (nums == null || nums.Length == 0){
         return null;
      }
      int[] newNums = nums.OrderBy(x => x).ToArray();
      for (int i = 0; i < newNums.Length; i++){
         for (int j = i; j < newNums.Length; j++){
            int left = j + 1;
            int right = newNums.Length - 1;
            while (left < right){
               int sum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
               if (sum == 0){
                  List<int> sums = new List<int>();
                  sums.Add(newNums[i]);
                  sums.Add(newNums[j]);
                  sums.Add(newNums[left]);
                  sums.Add(newNums[right]);
                  res.Add(sums);
                  int leftValue = newNums[left];
                  int rightValue = newNums[right];
                  while (left < nums.Length && leftValue == nums[left]){
                     left++;
                  }
                  while (right > left && right == nums[right]){
                     right--;
                  }
               }
               else if (sum < 0){
                  left++;
               }
               else{
                  right--;
               }
            }
            while (j + 1 < nums.Length && nums[j] == nums[j + 1]){
               j++;
            }
         }
         while (i + 1 < nums.Length && nums[i] == nums[i + 1]){
            i++;
         }
      }
      return res;
   }
}

static void Main(string[] args){
   Arrays s = new Arrays();
   int[] nums = { 1,0,-1,0,-2,2 };
   var ss = FourSum(nums);
   foreach (var item in ss){
      foreach (var item1 in item){
         Console.WriteLine(item1);
      }
   }
}

Ausgabe

[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Das obige ist der detaillierte Inhalt vonWie finde ich mit C# alle eindeutigen Quadrupel nahe Null?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!