从k个列表中查找包含元素的最小范围

原文：https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

给定k个大小为n的整数排序列表，从k个列表中的每一个中查找至少包含元素的最小范围。 如果找到多个最小范围，请打印其中任何一个。

示例：

Input: K = 3
arr1[] : [4, 7, 9, 12, 15]
arr2[] : [0, 8, 10, 14, 20]
arr3[] : [6, 12, 16, 30, 50]
Output:
The smallest range is [6 8]

Explanation: Smallest range is formed by 
number 7 from the first list, 8 from second
list and 6 from the third list.

Input: k = 3
arr1[] : [4, 7]
arr2[] : [1, 2]
arr3[] : [20, 40]
Output:
The smallest range is [2 20]

Explanation:The range [2, 20] contains 2, 4, 7, 20
which contains element from all the three arrays.

朴素的方法：给定K个排序列表，找到一个范围，其中每个列表中至少有一个元素。 解决问题的想法非常简单，通过将k个元素的最小值和最大值取为范围，可以将k个指针保持在范围内。 最初，所有指针将指向所有k个数组的开头。 存储范围从最大到最小。 如果必须将范围最小化，则必须增加最小值或必须减少最大值。 数组排序时不能减小最大值，但可以增大最小值。 要继续增加最小值，请增加包含最小值的列表的指针，并更新范围，直到其中一个列表用完。

• 算法：

  1. 创建一个长度为k的额外空间ptr，以存储指针和一个初始化为最大值的变量minrange。

  2. 最初，每个列表的索引为 0，因此将ptr[0..k]的每个元素初始化为 0，数组ptr将在范围内存储元素的索引。

  3. 重复以下步骤，直到至少一个列表为空：

     1. 现在，在由ptr[0…k]数组指向的所有列表的当前元素中找到最小值和最大值。

     2. 现在，如果当前（最大-最小值）小于最小范围，则更新最小范围。

     3. 递增指向当前最小元素的指针。

• 实现：

  C++

  ```cpp

  // C++ program to finds out smallest range that includes // elements from each of the given sorted lists.

  include

  using namespace std;

  define N 5

  // array for storing the current index of list i int ptr[501];

  // This function takes an k sorted lists in the form of // 2D array as an argument. It finds out smallest range // that includes elements from each of the k lists. void findSmallestRange(int arr[][N], int n, int k) {     int i, minval, maxval, minrange, minel, maxel, flag, minind;

  // initializing to 0 index;     for (i = 0; i <= k; i++)         ptr[i] = 0;

  minrange = INT_MAX;

  while (1) {         // for mainting the index of list containing the minimum element         minind = -1;         minval = INT_MAX;         maxval = INT_MIN;         flag = 0;

  // iterating over all the list         for (i = 0; i < k; i++) {             // if every element of list[i] is traversed then break the loop             if (ptr[i] == n) {                 flag = 1;                 break;             }             // find minimum value among all the list elements pointing by the ptr[] array             if (ptr[i] < n && arr[i][ptr[i]] < minval) {                 minind = i; // update the index of the list                 minval = arr[i][ptr[i]];             }             // find maximum value among all the list elements pointing by the ptr[] array             if (ptr[i] < n && arr[i][ptr[i]] > maxval) {                 maxval = arr[i][ptr[i]];             }         }

  // if any list exhaust we will not get any better answer, so break the while loop         if (flag)             break;

  ptr[minind]++;

  // updating the minrange         if ((maxval - minval) < minrange) {             minel = minval;             maxel = maxval;             minrange = maxel - minel;         }     }

  printf("The smallest range is [%d, %d]\n", minel, maxel); }

  // Driver program to test above function int main() {     int arr[][N] = {         { 4, 7, 9, 12, 15 },         { 0, 8, 10, 14, 20 },         { 6, 12, 16, 30, 50 }     };

  int k = sizeof(arr) / sizeof(arr[0]);

  findSmallestRange(arr, N, k);

  return 0; } // This code is contributed by Aditya Krishna Namdeo

  ```

  Java

  ```java

  // Java program to finds out smallest range that includes // elements from each of the given sorted lists. class GFG {

  static final int N = 5;

  // array for storing the current index of list i     static int ptr[] = new int[501];

  // This function takes an k sorted lists in the form of     // 2D array as an argument. It finds out smallest range     // that includes elements from each of the k lists.     static void findSmallestRange(int arr[][], int n, int k)     {         int i, minval, maxval, minrange, minel = 0, maxel = 0, flag, minind;

  // initializing to 0 index;         for (i = 0; i <= k; i++) {             ptr[i] = 0;         }

  minrange = Integer.MAX_VALUE;

  while (true) {             // for mainting the index of list containing the minimum element             minind = -1;             minval = Integer.MAX_VALUE;             maxval = Integer.MIN_VALUE;             flag = 0;

  // iterating over all the list             for (i = 0; i < k; i++) {                 // if every element of list[i] is traversed then break the loop                 if (ptr[i] == n) {                     flag = 1;                     break;                 }                 // find minimum value among all the list elements pointing by the ptr[] array                 if (ptr[i] < n && arr[i][ptr[i]] < minval) {                     minind = i; // update the index of the list                     minval = arr[i][ptr[i]];                 }                 // find maximum value among all the list elements pointing by the ptr[] array                 if (ptr[i] < n && arr[i][ptr[i]] > maxval) {                     maxval = arr[i][ptr[i]];                 }             }

  // if any list exhaust we will not get any better answer, so break the while loop             if (flag == 1) {                 break;             }

  ptr[minind]++;

  // updating the minrange             if ((maxval - minval) < minrange) {                 minel = minval;                 maxel = maxval;                 minrange = maxel - minel;             }         }         System.out.printf("The smallest range is [%d, %d]\n", minel, maxel);     }

  // Driver program to test above function     public static void main(String[] args)     {

  int arr[][] = {             { 4, 7, 9, 12, 15 },             { 0, 8, 10, 14, 20 },             { 6, 12, 16, 30, 50 }         };

  int k = arr.length;

  findSmallestRange(arr, N, k);     } } // this code contributed by Rajput-Ji

  ```

  Python

  ```

  Python3 program to finds out

  smallest range that includes

  elements from each of the

  given sorted lists.

  N = 5

  array for storing the

  current index of list i

  ptr = [0 for i in range(501)]

  This function takes an k sorted

  lists in the form of 2D array as

  an argument. It finds out smallest

  range that includes elements from

  each of the k lists.

  def findSmallestRange(arr, n, k):

  i, minval, maxval, minrange, minel, maxel, flag, minind = 0, 0, 0, 0, 0, 0, 0, 0

  # initializing to 0 index     for i in range(k + 1):         ptr[i] = 0

  minrange = 10**9

  while(1):    

  # for mainting the index of list              # containing the minimum element         minind = -1         minval = 109         maxval = -109         flag = 0

  # iterating over all the list         for i in range(k):

  # if every element of list[i] is                  # traversed then break the loop             if(ptr[i] == n):                 flag = 1                     break

  # find minimum value among all the list              # elements pointing by the ptr[] array              if(ptr[i] < n and arr[i][ptr[i]] < minval):                 minind = i # update the index of the list                 minval = arr[i][ptr[i]]

  # find maximum value among all the              # list elements pointing by the ptr[] array             if(ptr[i] < n and arr[i][ptr[i]] > maxval):                 maxval = arr[i][ptr[i]]

  # if any list exhaust we will          # not get any better answer,         # so break the while loop         if(flag):             break

  ptr[minind] += 1

  # updating the minrange         if((maxval-minval) < minrange):             minel = minval             maxel = maxval             minrange = maxel - minel

  print("The smallest range is [", minel, maxel, "]")

  Driver code

  arr = [     [4, 7, 9, 12, 15],     [0, 8, 10, 14, 20],     [6, 12, 16, 30, 50]     ]

  k = len(arr)

  findSmallestRange(arr, N, k)

  This code is contributed by mohit kumar

  ```

  C

  ```cs

  // C# program to finds out smallest // range that includes elements from // each of the given sorted lists. using System;

  class GFG {

  static int N = 5;

  // array for storing the current index of list i     static int[] ptr = new int[501];

  // This function takes an k sorted     // lists in the form of 2D array as     // an argument. It finds out smallest range     // that includes elements from each of the k lists.     static void findSmallestRange(int[, ] arr,                                   int n, int k)     {         int i, minval, maxval, minrange,             minel = 0, maxel = 0, flag, minind;

  // initializing to 0 index;         for (i = 0; i <= k; i++) {             ptr[i] = 0;         }

  minrange = int.MaxValue;

  while (true) {             // for mainting the index of             // list containing the minimum element             minind = -1;             minval = int.MaxValue;             maxval = int.MinValue;             flag = 0;

  // iterating over all the list             for (i = 0; i < k; i++) {                 // if every element of list[i]                 // is traversed then break the loop                 if (ptr[i] == n) {                     flag = 1;                     break;                 }

  // find minimum value among all the                 // list elements pointing by the ptr[] array                 if (ptr[i] < n && arr[i, ptr[i]] < minval) {                     minind = i; // update the index of the list                     minval = arr[i, ptr[i]];                 }

  // find maximum value among all the                 // list elements pointing by the ptr[] array                 if (ptr[i] < n && arr[i, ptr[i]] > maxval) {                     maxval = arr[i, ptr[i]];                 }             }

  // if any list exhaust we will             // not get any better answer,             // so break the while loop             if (flag == 1) {                 break;             }

  ptr[minind]++;

  // updating the minrange             if ((maxval - minval) < minrange) {                 minel = minval;                 maxel = maxval;                 minrange = maxel - minel;             }         }         Console.WriteLine("The smallest range is"                               + "[{0}, {1}]\n",                           minel, maxel);     }

  // Driver code     public static void Main(String[] args)     {

  int[, ] arr = {             { 4, 7, 9, 12, 15 },             { 0, 8, 10, 14, 20 },             { 6, 12, 16, 30, 50 }         };

  int k = arr.GetLength(0);

  findSmallestRange(arr, N, k);     } }

  // This code has been contributed by 29AjayKumar

  ```

• 输出：

  The smallest range is [6 8]

• 复杂度分析：

  • 时间复杂度：O(n * k ^ 2)，要找到长度为k的数组中的最大值和最小值，所需时间为O(K)，并遍历所有k长度为n的数组（在最坏的情况下），时间复杂度为O(N * K)，则总时间复杂度为O(n * k ^ 2)。

  • 空间复杂度：O(K)，需要一个长度为k的额外数组，因此空间复杂度为O(K)。

高效方法：该方法保持不变，但是可以通过使用最小堆或优先级队列来降低时间复杂度。 最小堆可用于以对数时间或log k时间而不是线性时间来查找最大值和最小值。 其余方法保持不变。

• 算法：

  1. 创建一个最小堆来存储k个元素，每个数组一个，并将初始化为最大值的变量minrange初始化为最大值，还保留一个变量max以存储最大整数。

  2. 最初，将每个列表中每个元素的第一个元素放置在max中。

  3. 重复以下步骤，直到至少一个列表为空：

     1. 要查找最小值或min，请使用最小堆的顶部或根，它是最小元素。

     2. 现在，如果当前（最大减最小值）小于最小范围，则更新最小范围。

     3. 从优先级队列中删除顶部或根元素，然后从列表中插入包含min元素的下一个元素，并使用插入的新元素更新max。

• 实现：

  C++

  ```cpp

  // C++ program to finds out smallest range that includes // elements from each of the given sorted lists.

  include

  using namespace std;

  define N 5

  // A min heap node struct MinHeapNode {     // The element to be stored     int element;

  // index of the list from which the element is taken     int i;

  // index of the next element to be picked from list     int j; };

  // Prototype of a utility function to swap two min heap nodes void swap(MinHeapNode x, MinHeapNode y);

  // A class for Min Heap class MinHeap {

  // pointer to array of elements in heap     MinHeapNode* harr;

  // size of min heap     int heap_size;

  public:     // Constructor: creates a min heap of given size     MinHeap(MinHeapNode a[], int size);

  // to heapify a subtree with root at given index     void MinHeapify(int);

  // to get index of left child of node at index i     int left(int i) { return (2 * i + 1); }

  // to get index of right child of node at index i     int right(int i) { return (2 * i + 2); }

  // to get the root     MinHeapNode getMin() { return harr[0]; }

  // to replace root with new node x and heapify() new root     void replaceMin(MinHeapNode x)     {         harr[0] = x;         MinHeapify(0);     } };

  // Constructor: Builds a heap from a // given array a[] of given size MinHeap::MinHeap(MinHeapNode a[], int size) {     heap_size = size;     harr = a; // store address of array     int i = (heap_size - 1) / 2;     while (i >= 0) {         MinHeapify(i);         i--;     } }

  // A recursive method to heapify a subtree with root at // given index. This method assumes that the subtrees // are already heapified void MinHeap::MinHeapify(int i) {     int l = left(i);     int r = right(i);     int smallest = i;     if (l < heap_size && harr[l].element < harr[i].element)         smallest = l;     if (r < heap_size && harr[r].element < harr[smallest].element)         smallest = r;     if (smallest != i) {         swap(harr[i], harr[smallest]);         MinHeapify(smallest);     } }

  // This function takes an k sorted lists in the form of // 2D array as an argument. It finds out smallest range // that includes elements from each of the k lists. void findSmallestRange(int arr[][N], int k) {     // Create a min heap with k heap nodes. Every heap node     // has first element of an list     int range = INT_MAX;     int min = INT_MAX, max = INT_MIN;     int start, end;

  MinHeapNode* harr = new MinHeapNode[k];     for (int i = 0; i < k; i++) {         // Store the first element         harr[i].element = arr[i][0];

  // index of list         harr[i].i = i;

  // Index of next element to be stored         // from list         harr[i].j = 1;

  // store max element         if (harr[i].element > max)             max = harr[i].element;     }

  // Create the heap     MinHeap hp(harr, k);

  // Now one by one get the minimum element from min     // heap and replace it with next element of its list     while (1) {         // Get the minimum element and store it in output         MinHeapNode root = hp.getMin();

  // update min         min = hp.getMin().element;

  // update range         if (range > max - min + 1) {             range = max - min + 1;             start = min;             end = max;         }

  // Find the next element that will replace current         // root of heap. The next element belongs to same         // list as the current root.         if (root.j < N) {             root.element = arr[root.i][root.j];             root.j += 1;

  // update max element             if (root.element > max)                 max = root.element;         }

  // break if we have reached end of any list         else             break;

  // Replace root with next element of list         hp.replaceMin(root);     }

  cout << "The smallest range is "          << "["          << start << " " << end << "]" << endl;     ; }

  // Driver program to test above functions int main() {     int arr[][N] = {         { 4, 7, 9, 12, 15 },         { 0, 8, 10, 14, 20 },         { 6, 12, 16, 30, 50 }     };     int k = sizeof(arr) / sizeof(arr[0]);

  findSmallestRange(arr, k);

  return 0; }

  ```

  Java

  ```java

  // Java program to find out smallest // range that includes elements from // each of the given sorted lists. class GFG {

  // A min heap node     static class Node {         // The element to be stored         int ele;

  // index of the list from which         // the element is taken         int i;

  // index of the next element         // to be picked from list         int j;

  Node(int a, int b, int c)         {             this.ele = a;             this.i = b;             this.j = c;         }     }

  // A class for Min Heap     static class MinHeap {         Node[] harr; // array of elements in heap         int size; // size of min heap

  // Constructor: creates a min heap         // of given size         MinHeap(Node[] arr, int size)         {             this.harr = arr;             this.size = size;             int i = (size - 1) / 2;             while (i >= 0) {                 MinHeapify(i);                 i--;             }         }

  // to get index of left child         // of node at index i         int left(int i)         {             return 2 * i + 1;         }

  // to get index of right child         // of node at index i         int right(int i)         {             return 2 * i + 2;         }

  // to heapify a subtree with         // root at given index         void MinHeapify(int i)         {             int l = left(i);             int r = right(i);             int small = i;             if (l < size && harr[l].ele < harr[i].ele)                 small = l;             if (r < size && harr[r].ele < harr[small].ele)                 small = r;             if (small != i) {                 swap(small, i);                 MinHeapify(small);             }         }

  void swap(int i, int j)         {             Node temp = harr[i];             harr[i] = harr[j];             harr[j] = temp;         }

  // to get the root         Node getMin()         {             return harr[0];         }

  // to replace root with new node x         // and heapify() new root         void replaceMin(Node x)         {             harr[0] = x;             MinHeapify(0);         }     }

  // This function takes an k sorted lists     // in the form of 2D array as an argument.     // It finds out smallest range that includes     // elements from each of the k lists.     static void findSmallestRange(int[][] arr, int k)     {         int range = Integer.MAX_VALUE;         int min = Integer.MAX_VALUE;         int max = Integer.MIN_VALUE;         int start = -1, end = -1;

  int n = arr[0].length;

  // Create a min heap with k heap nodes.         // Every heap node has first element of an list         Node[] arr1 = new Node[k];         for (int i = 0; i < k; i++) {             Node node = new Node(arr[i][0], i, 1);             arr1[i] = node;

  // store max element             max = Math.max(max, node.ele);         }

  // Create the heap         MinHeap mh = new MinHeap(arr1, k);

  // Now one by one get the minimum element         // from min heap and replace it with         // next element of its list         while (true) {             // Get the minimum element and             // store it in output             Node root = mh.getMin();

  // update min             min = root.ele;

  // update range             if (range > max - min + 1) {                 range = max - min + 1;                 start = min;                 end = max;             }

  // Find the next element that will             // replace current root of heap.             // The next element belongs to same             // list as the current root.             if (root.j < n) {                 root.ele = arr[root.i][root.j];                 root.j++;

  // update max element                 if (root.ele > max)                     max = root.ele;             }             // break if we have reached             // end of any list             else                 break;

  // Replace root with next element of list             mh.replaceMin(root);         }         System.out.print("The smallest range is [" + start + " " + end + "]");     }

  // Driver Code     public static void main(String[] args)     {         int arr[][] = { { 4, 7, 9, 12, 15 },                         { 0, 8, 10, 14, 20 },                         { 6, 12, 16, 30, 50 } };

  int k = arr.length;

  findSmallestRange(arr, k);     } }

  // This code is contributed by nobody_cares

  ```

  C

  ```cs

  // C# program to find out smallest // range that includes elements from // each of the given sorted lists. using System; using System.Collections.Generic;

  class GFG {

  // A min heap node     public class Node {         // The element to be stored         public int ele;

  // index of the list from which         // the element is taken         public int i;

  // index of the next element         // to be picked from list         public int j;

  public Node(int a, int b, int c)         {             this.ele = a;             this.i = b;             this.j = c;         }     }

  // A class for Min Heap     public class MinHeap {         // array of elements in heap         public Node[] harr;

  // size of min heap         public int size;

  // Constructor: creates a min heap         // of given size         public MinHeap(Node[] arr, int size)         {             this.harr = arr;             this.size = size;             int i = (size - 1) / 2;             while (i >= 0) {                 MinHeapify(i);                 i--;             }         }

  // to get index of left child         // of node at index i         int left(int i)         {             return 2 * i + 1;         }

  // to get index of right child         // of node at index i         int right(int i)         {             return 2 * i + 2;         }

  // to heapify a subtree with         // root at given index         void MinHeapify(int i)         {             int l = left(i);             int r = right(i);             int small = i;             if (l < size && harr[l].ele < harr[i].ele)                 small = l;             if (r < size && harr[r].ele < harr[small].ele)                 small = r;             if (small != i) {                 swap(small, i);                 MinHeapify(small);             }         }

  void swap(int i, int j)         {             Node temp = harr[i];             harr[i] = harr[j];             harr[j] = temp;         }

  // to get the root         public Node getMin()         {             return harr[0];         }

  // to replace root with new node x         // and heapify() new root         public void replaceMin(Node x)         {             harr[0] = x;             MinHeapify(0);         }     }

  // This function takes an k sorted lists     // in the form of 2D array as an argument.     // It finds out smallest range that includes     // elements from each of the k lists.     static void findSmallestRange(int[, ] arr, int k)     {         int range = int.MaxValue;         int min = int.MaxValue;         int max = int.MinValue;         int start = -1, end = -1;

  int n = arr.GetLength(0);

  // Create a min heap with k heap nodes.         // Every heap node has first element of an list         Node[] arr1 = new Node[k];         for (int i = 0; i < k; i++) {             Node node = new Node(arr[i, 0], i, 1);             arr1[i] = node;

  // store max element             max = Math.Max(max, node.ele);         }

  // Create the heap         MinHeap mh = new MinHeap(arr1, k);

  // Now one by one get the minimum element         // from min heap and replace it with         // next element of its list         while (true) {             // Get the minimum element and             // store it in output             Node root = mh.getMin();

  // update min             min = root.ele;

  // update range             if (range > max - min + 1) {                 range = max - min + 1;                 start = min;                 end = max;             }

  // Find the next element that will             // replace current root of heap.             // The next element belongs to same             // list as the current root.             if (root.j < n) {                 root.ele = arr[root.i, root.j];                 root.j++;

  // update max element                 if (root.ele > max)                     max = root.ele;             }             else                 break; // break if we have reached             // end of any list

  // Replace root with next element of list             mh.replaceMin(root);         }         Console.Write("The smallest range is [" + start + " " + end + "]");     }

  // Driver Code     public static void Main(String[] args)     {         int[, ] arr = { { 4, 7, 9, 12, 15 },                         { 0, 8, 10, 14, 20 },                         { 6, 12, 16, 30, 50 } };

  int k = arr.GetLength(0);

  findSmallestRange(arr, k);     } }

  // This code is contributed by Rajput-Ji

  ```

• 输出：

  The smallest range is [6 8]

• 复杂度分析：

  • 时间复杂度：O(n * k * log k)。

    为了找到长度为k的最小堆中的最大值和最小值，所需时间为O(log k)，并遍历所有长度为n的k个数组（在最坏的情况下），时间复杂度为O(N * K)，则总时间复杂度为O(n * k * log k)。

  • 空间复杂度：O(K)。

    优先级队列将存储k个元素，因此空间复杂度为O(K)。

本文由 Aditya Goel 提供。 如果您喜欢 GeeksforGeeks 并希望做出贡献，那么您也可以写一篇文章，并将您的文章邮寄到 contribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。

如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请发表评论。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/34036.html