Comment trouver tous les quadruples uniques proches de zéro en utilisant C# ?-Tutoriel C#.Net-php.cn

Comment trouver tous les quadruples uniques proches de zéro en utilisant C# ?

WBOY

Libérer： 2023-09-22 15:37:02

avant

996 Les gens l'ont consulté

如何使用 C# 找到所有接近于零的唯一四元组？

Le moyen le plus simple est de créer quatre boucles imbriquées et de vérifier une par une si la somme des quatre éléments est nulle. Si la somme des quatre éléments est nulle, imprimez les éléments.

Complexité temporelle - O(n⁴)

- O(1)

Nous pouvons utiliser une structure de données d'ensemble non ordonnée pour stocker chaque valeur du tableau. Set offre l'avantage de rechercher des éléments en un temps O(1). Ainsi, pour chaque paire du tableau, nous chercherons la valeur négative de leur somme qui peut exister dans l'ensemble. Si un tel élément est trouvé alors nous pouvons imprimer un triplet qui sera une paire d'entiers et la valeur négative de leur somme.

Complexité temporelle - O(n³)

Complexité spatiale - O(n)

Exemple

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);
      }
   }
}

Copier après la connexion