Tìm cửa sổ nhỏ nhất của mảng đầu vào chứa tất cả các phần tử của mảng truy vấn

Question

Vấn đề: Cho một mảng đầu vào của các số nguyên có kích thước n và một mảng truy vấn các số nguyên k kích thước, tìm cửa sổ nhỏ nhất của mảng đầu vào chứa tất cả các phần tử của mảng truy vấn và cũng có cùng thứ tự.

Tôi đã thử phương pháp tiếp cận bên dưới.

 int[] inputArray = new int[] { 2, 5, 2, 8, 0, 1, 4, 7 }; 
     int[] queryArray = new int[] { 2, 1, 7 }; 

Sẽ tìm vị trí của tất cả phần tử mảng truy vấn trong inputArray.

public static void SmallestWindow(int[] inputArray, int[] queryArray) 
    { 
     Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>(); 

     int index = 0; 
     foreach (int i in queryArray) 
     { 
      HashSet<int> hash = new HashSet<int>(); 
      foreach (int j in inputArray) 
      { 
       index++; 
       if (i == j) 
        hash.Add(index); 
      } 
      dict.Add(i, hash); 
      index = 0; 
     } 
     // Need to perform action in above dictionary.?? 
    } 

tôi đã theo từ điển

1. int 2 -> vị trí {1, 3}
2. int 1 -> vị trí {6}
3. int 7 -> vị trí { 8}

Bây giờ tôi muốn thực hiện bước sau để tìm ra cửa sổ tối thiểu

1. So sánh vị trí int 2 với vị trí int 1. Như (6-3) < (6-1) .. Vì vậy, tôi sẽ lưu trữ 3, 6 trong một hashmap.

2. Sẽ so sánh vị trí của int 1 và int 7 giống như ở trên.

Tôi không thể hiểu cách tôi so sánh hai giá trị liên tiếp của từ điển. Hãy giúp tôi.

Answer 1

Tôi không thấy cách sử dụng HashSet và Dictionary sẽ giúp bạn trong việc này. Tôi đã phải đối mặt với vấn đề này, tôi sẽ đi về nó khá khác nhau.

Một cách để thực hiện (không phải cách hiệu quả nhất) được hiển thị bên dưới. Mã này giả định rằng queryArray chứa ít nhất hai mục.

int FindInArray(int[] a, int start, int value) 
{ 
    for (int i = start; i < a.Length; ++i) 
    { 
     if (a[i] == value) 
      return i; 
    } 
    return -1; 
} 

struct Pair 
{ 
    int first; 
    int last; 
} 

List<Pair> foundPairs = new List<Pair>(); 

int startPos = 0; 
bool found = true; 
while (found) 
{ 
    found = false; 
    // find next occurrence of queryArray[0] in inputArray 
    startPos = FindInArray(inputArray, startPos, queryArray[0]); 
    if (startPos == -1) 
    { 
     // no more occurrences of the first item 
     break; 
    } 
    Pair p = new Pair(); 
    p.first = startPos; 
    ++startPos; 
    int nextPos = startPos; 
    // now find occurrences of remaining items 
    for (int i = 1; i < queryArray.Length; ++i) 
    { 
     nextPos = FindInArray(inputArray, nextPos, queryArray[i]); 
     if (nextPos == -1) 
     { 
      break; // didn't find it 
     } 
     else 
     { 
      p.last = nextPos++; 
      found = (i == queryArray.Length-1); 
     } 
    } 
    if (found) 
    { 
     foundPairs.Add(p); 
    } 
} 

// At this point, the foundPairs list contains the (start, end) of all 
// sublists that contain the items in order. 
// You can then iterate through that list, subtract (last-first), and take 
// the item that has the smallest value. That will be the shortest sublist 
// that matches the criteria. 

Với một số công việc, điều này có thể được thực hiện hiệu quả hơn. Ví dụ: nếu 'queryArray' chứa [1, 2, 3] và inputArray chứa [1, 7, 4, 9, 1, 3, 6, 4, 1, 8, 2, 3], mã ở trên sẽ tìm thấy ba kết quả phù hợp (bắt đầu từ vị trí 0, 4 và 8). Mã thông minh nhẹ hơn có thể xác định rằng khi tìm thấy 1 ở vị trí 4, vì không tìm thấy 2 trước đó, bất kỳ chuỗi nào bắt đầu ở vị trí đầu tiên sẽ dài hơn chuỗi bắt đầu ở vị trí 4 và do đó ngắn mạch đầu tiên và bắt đầu lại ở vị trí mới. Điều đó làm phức tạp mã một chút, mặc dù.

Answer 2

Thuật toán:
Đối với mỗi phần tử trong mảng truy vấn, lưu trữ trong một M bản đồ (V → (I, P)), V là yếu tố, tôi là một chỉ số vào mảng đầu vào, P là vị trí trong mảng truy vấn. (Chỉ mục vào mảng đầu vào cho một số P là lớn nhất sao cho truy vấn [0..P] là một chuỗi đầu vào [I..curr])

Lặp lại qua mảng.
Nếu giá trị là cụm từ đầu tiên trong mảng truy vấn: Lưu trữ chỉ mục hiện tại là I.
Khác: Lưu trữ giá trị của chỉ mục của phần tử trước đó trong mảng truy vấn, ví dụ: M[currVal].I = M[query[M[currVal].P-1]].I.
Nếu giá trị là thuật ngữ cuối cùng: Kiểm tra xem [I..curr] có phải là mới hay không.

phức tạp
Sự phức tạp của việc này là O (N), trong đó N là kích thước của mảng đầu vào.

N.B.
Mã này hy vọng rằng không có phần tử nào được lặp lại trong mảng truy vấn. Để phục vụ cho điều này, chúng ta có thể sử dụng một bản đồ M (V → listOf ((I, P))). Đây là O (N hC (Q)), trong đó hC (Q) là số của chế độ cho mảng truy vấn ..
Thậm chí tốt hơn là sử dụng M (V → listOf ((linkedList (I), P))). Trong trường hợp các phần tử lặp lại xuất hiện liên tiếp trong mảng truy vấn, chúng tôi sử dụng danh sách được liên kết. Cập nhật các giá trị đó sau đó trở thành O (1). Độ phức tạp sau đó là O (N hC (D (Q))), trong đó D (Q) là Q với các từ liên tiếp được hợp nhất.

Thực hiện
Mẫu java thực hiện có sẵn here. Điều này không hoạt động đối với các phần tử lặp lại trong mảng truy vấn, cũng như không kiểm tra lỗi, v.v.

Answer 3

Bạn không muốn HashSet nhưng một (hoặc) sắp xếp) làm giá trị trong từ điển; từ điển chứa ánh xạ từ các giá trị bạn tìm thấy trong mảng đầu vào vào danh sách các chỉ mục có giá trị đó xuất hiện.

Sau đó, bạn làm như sau

• Tra cứu mục đầu tiên trong truy vấn. Chọn chỉ mục thấp nhất nơi nó xuất hiện.
• Tra cứu mục nhập thứ hai; chọn mục nhập thấp nhất lớn hơn chỉ mục đầu tiên.
• Tra cứu thứ ba; chọn mức thấp nhất lớn hơn thứ hai. (Vv)
• Khi bạn đến mục nhập cuối cùng trong truy vấn, (1 + chỉ mục cuối cùng - chỉ mục đầu tiên) là kích thước của kết quả phù hợp nhỏ nhất.
• Bây giờ hãy chọn chỉ mục thứ hai của truy vấn đầu tiên, lặp lại, v.v.
• Chọn kết quả phù hợp nhỏ nhất được tìm thấy từ bất kỳ chỉ mục bắt đầu nào.

(Lưu ý rằng "nhập lớn hơn mức thấp nhất" là một hoạt động cung cấp với cây được sắp xếp, hoặc có thể được tìm thấy thông qua tìm kiếm nhị phân trên một mảng được sắp xếp.)

Sự phức tạp của việc này là khoảng O(M*n*log n) nơi M là độ dài của truy vấn và n là số chỉ số trung bình mà tại đó giá trị đã cho xuất hiện trong mảng đầu vào. Bạn có thể sửa đổi chiến lược bằng cách chọn giá trị mảng truy vấn xuất hiện ít nhất là thường xuyên cho điểm bắt đầu và đi lên và xuống từ đó; nếu có k trong số các mục nhập đó (k < = n) thì độ phức tạp là O(M*k*log n).

Answer 4

Sau khi bạn có tất cả các vị trí (chỉ số) trong inputArray:

2 --> position {0,2} // note: I change them to 0-based array 
1 --> position {5,6} // I suppose it's {5,6} to make it more complex, in your code it's only {5} 
7 --> position {7} 

tôi sử dụng một đệ quy để có được tất cả các đường dẫn có thể. [0-> 5-> 7] [0-> 6-> 7] [2-> 5-> 7] [2-> 6-> 7]. Tổng số là 2 * 2 * 1 = 4 đường dẫn có thể. Rõ ràng một trong những người có Min(Last-First) là con đường ngắn nhất (cửa sổ nhỏ nhất), những con số ở giữa con đường không quan trọng. Ở đây có mã.

struct Pair 
{ 
    public int Number; // the number in queryArray 
    public int[] Indexes; // the positions of the number 
} 
static List<int[]> results = new List<int[]>(); //store all possible paths 
static Stack<int> currResult = new Stack<int>(); // the container of current path 
static int[] inputArray, queryArray; 
static Pair[] pairs; 

Sau cấu trúc dữ liệu, đây là Main.

inputArray = new int[] { 2, 7, 1, 5, 2, 8, 0, 1, 4, 7 }; //my test case 
queryArray = new int[] { 2, 1, 7 }; 
pairs = (from n in queryArray 
     select new Pair { Number = n, Indexes = inputArray.FindAllIndexes(i => i == n) }).ToArray(); 
Go(0); 

FindAllIndexes là một phương pháp tiện ích để giúp tìm tất cả các chỉ mục.

public static int[] FindAllIndexes<T>(this IEnumerable<T> source, Func<T,bool> predicate) 
{ 
    //do necessary check here, then 
    Queue<int> indexes = new Queue<int>(); 
    for (int i = 0;i<source.Count();i++) 
      if (predicate(source.ElementAt(i))) indexes.Enqueue(i); 
    return indexes.ToArray(); 
} 

Phương pháp đệ quy:

static void Go(int depth) 
{ 
    if (depth == pairs.Length) 
    { 
     results.Add(currResult.Reverse().ToArray()); 
    } 
    else 
    { 
     var indexes = pairs[depth].Indexes; 
     for (int i = 0; i < indexes.Length; i++) 
     { 
      if (depth == 0 || indexes[i] > currResult.Last()) 
      { 
       currResult.Push(indexes[i]); 
       Go(depth + 1); 
       currResult.Pop(); 
      } 
     } 
    } 
} 

Cuối cùng, một vòng lặp của results có thể tìm thấy Min(Last-First) kết quả (cửa sổ ngắn nhất).

Answer 5

Thuật toán:

1. nhận được tất cả các chỉ số vào inputArray của tất cả queryArray giá trị
2. sắp xếp chúng tăng dần theo chỉ số
3. sử dụng mỗi chỉ số (x) như là một bắt đầu điểm tìm ra chỉ số cao đầu tiên (y) sao cho phân khúc inputArray [xy] chứa tất cả truy vấnCác giá trị của mảng
4. chỉ giữ lại những phân đoạn có mục queryArray để
5. trật tự các phân đoạn bằng chiều dài của họ, tăng dần

C# thực hiện:

đầu tiên nhận được tất cả các chỉ số vào inputArray của tất cả các giá trị queryArray và sắp xếp chúng tăng dần theo chỉ số.

public static int[] SmallestWindow(int[] inputArray, int[] queryArray) 
{ 
    var indexed = queryArray 
     .SelectMany(x => inputArray 
          .Select((y, i) => new 
           { 
            Value = y, 
            Index = i 
           }) 
          .Where(y => y.Value == x)) 
     .OrderBy(x => x.Index) 
     .ToList(); 

Tiếp theo, sử dụng mỗi chỉ số (x) như là một điểm khởi đầu tìm người đầu tiên cao hơn chỉ số (y) sao cho phân khúc inputArray [x-y] chứa tất cả các giá trị queryArray.

var segments = indexed 
     .Select(x => 
      { 
       var unique = new HashSet<int>(); 
       return new 
        { 
         Item = x, 
         Followers = indexed 
          .Where(y => y.Index >= x.Index) 
          .TakeWhile(y => unique.Count != queryArray.Length) 
          .Select(y => 
           { 
            unique.Add(y.Value); 
            return y; 
           }) 
          .ToList(), 
         IsComplete = unique.Count == queryArray.Length 
        }; 
      }) 
     .Where(x => x.IsComplete); 

Bây giờ chỉ giữ lại những phân đoạn có truy vấnArray mục theo thứ tự.

var queryIndexed = segments 
     .Select(x => x.Followers.Select(y => new 
      { 
       QIndex = Array.IndexOf(queryArray, y.Value), 
       y.Index, 
       y.Value 
      }).ToArray()); 

    var queryOrdered = queryIndexed 
     .Where(item => 
      { 
       var qindex = item.Select(x => x.QIndex).ToList(); 
       bool changed; 
       do 
       { 
        changed = false; 
        for (int i = 1; i < qindex.Count; i++) 
        { 
         if (qindex[i] <= qindex[i - 1]) 
         { 
          qindex.RemoveAt(i); 
          changed = true; 
         } 
        } 
       } while (changed); 
       return qindex.Count == queryArray.Length; 
      }); 

Cuối cùng, sắp xếp các đoạn theo độ dài của chúng, tăng dần. Phân đoạn đầu tiên trong kết quả là cửa sổ nhỏ nhất vào inputArray chứa tất cả các giá trị queryArray theo thứ tự của queryArray.

var result = queryOrdered 
     .Select(x => new[] 
      { 
       x.First().Index, 
       x.Last().Index 
      }) 
     .OrderBy(x => x[1] - x[0]); 

    var best = result.FirstOrDefault(); 
    return best; 
} 

thử nghiệm nó với

public void Test() 
{ 
    var inputArray = new[] { 2, 1, 5, 6, 8, 1, 8, 6, 2, 9, 2, 9, 1, 2 }; 
    var queryArray = new[] { 6, 1, 2 }; 

    var result = SmallestWindow(inputArray, queryArray); 

    if (result == null) 
    { 
     Console.WriteLine("no matching window"); 
    } 
    else 
    { 
     Console.WriteLine("Smallest window is indexes " + result[0] + " to " + result[1]); 
    } 
} 

đầu ra:

Smallest window is indexes 3 to 8 

Answer 6

Cảm ơn mọi người vì những đóng góp của bạn. Tôi đã thay đổi mã của tôi một chút và thấy nó hoạt động. Mặc dù nó có thể không phải là rất hiệu quả nhưng tôi hạnh phúc để giải quyết bằng cách sử dụng đầu của tôi :). Xin vui lòng cho ý kiến ​​phản hồi của bạn

Đây là lớp Pair tôi với có số lượng và vị trí như biến

public class Pair 
    { 
    public int Number; 
    public List<int> Position; 
    } 

Dưới đây là một phương pháp mà sẽ trả về danh sách của tất cả các cặp.

 public static Pair[] GetIndex(int[] inputArray, int[] query) 
     { 
     Pair[] pairList = new Pair[query.Length]; 
     int pairIndex = 0; 
     foreach (int i in query) 
     { 
      Pair pair = new Pair(); 
      int index = 0; 
      pair.Position = new List<int>(); 
      foreach (int j in inputArray) 
      {      
       if (i == j) 
       { 
        pair.Position.Add(index); 
       } 
       index++; 
      } 
      pair.Number = i; 
      pairList[pairIndex] = pair; 
      pairIndex++; 
     } 
     return pairList; 
    } 

Đây là dòng mã trong phương thức Main

 Pair[] pairs = NewCollection.GetIndex(array, intQuery); 

     List<int> minWindow = new List<int>(); 
     for (int i = 0; i <pairs.Length - 1; i++) 
     { 
      List<int> first = pairs[i].Position; 
      List<int> second = pairs[i + 1].Position; 
      int? temp = null; 
      int? temp1 = null; 
      foreach(int m in first) 
      { 
       foreach (int n in second) 
       { 
        if (n > m) 
        { 
         temp = m; 
         temp1 = n; 
        }       
       }      
      } 
      if (temp.HasValue && temp1.HasValue) 
      { 
       if (!minWindow.Contains((int)temp)) 
        minWindow.Add((int)temp); 
       if (!minWindow.Contains((int)temp1)) 
        minWindow.Add((int)temp1); 
      } 
      else 
      { 
       Console.WriteLine(" Bad Query array"); 
       minWindow.Clear(); 
       break;      
      } 
     } 

     if(minWindow.Count > 0) 
     { 
     Console.WriteLine("Minimum Window is :"); 
     foreach(int i in minWindow) 
     { 
      Console.WriteLine(i + " "); 
     } 
     } 

Answer 7

Nó là đáng chú ý rằng vấn đề này có liên quan đến vấn đề dãy chung dài nhất, vì vậy đến với thuật toán chạy trong tốt hơn so với O (n^2) thời gian trong trường hợp chung với các bản sao sẽ là một thách thức.

Answer 8

Chỉ trong trường hợp ai đó đang quan tâm đến việc thực hiện ++ C với O (nlog (k))

void findMinWindow(const vector<int>& input, const vector<int>& query) { 
     map<int, int> qtree; 
     for(vector<int>::const_iterator itr=query.begin(); itr!=query.end(); itr++) { 
      qtree[*itr] = 0; 
     } 

     int first_ptr=0; 
     int begin_ptr=0; 

     int index1 = 0; 
     int queptr = 0; 

     int flip = 0; 

     while(true) { 
      //check if value is in query 
      if(qtree.find(input[index1]) != qtree.end()) { 
       int x = qtree[input[index1]]; 
       if(0 == x) { 
        flip++; 
       } 
       qtree[input[index1]] = ++x; 
       } 

       //remove all nodes that are not required and 
       //yet satisfy the all query condition. 
       while(query.size() == flip) { 
       //done nothing more 
       if(queptr == input.size()) { 
        break; 
       } 

       //check if queptr is pointing to node in the query 
       if(qtree.find(input[queptr]) != qtree.end()) { 
        int y = qtree[input[queptr]]; 
        //more nodes and the queue is pointing to deleteable node 
        //condense the nodes 
        if(y > 1) { 
        qtree[input[queptr]] = --y; 
        queptr++; 
        } else { 
        //cant condense more just keep that memory 
        if((!first_ptr && !begin_ptr) || 
         ((first_ptr-begin_ptr)>(index1-queptr))) { 
         first_ptr=index1; 
         begin_ptr=queptr; 
        } 
        break; 
        } 
       } else { 
        queptr++; 
       } 
       } 

      index1++; 

      if(index1==input.size()) { 
       break; 
      } 
     } 
     cout<<"["<<begin_ptr<<" - "<<first_ptr<<"]"<<endl; 
    } 

đây chính để gọi nó.

#include <iostream> 
    #include <vector> 
    #include <map> 

    using namespace std; 

    int main() { 
     vector<int> input; 
     input.push_back(2); 
     input.push_back(5); 
     input.push_back(2); 
     input.push_back(8); 
     input.push_back(0); 
     input.push_back(1); 
     input.push_back(4); 
     input.push_back(7); 

     vector<int> query1; 
     query1.push_back(2); 
     query1.push_back(8); 
     query1.push_back(0); 

     vector<int> query2; 
     query2.push_back(2); 
     query2.push_back(1); 
     query2.push_back(7); 

     vector<int> query3; 
     query3.push_back(1); 
     query3.push_back(4); 

     findMinWindow(input, query1); 
     findMinWindow(input, query2); 
     findMinWindow(input, query3); 
    }