Greedy Algorithm to Find the Lexicographically Smallest Sequence

  • 时间:2020-10-07 14:38:56
  • 分类:网络文摘
  • 阅读:83 次

Given a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.

Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

1
int[] findMinArray(int[] arr, int k)
int[] findMinArray(int[] arr, int k)

Input
n is in the range [1, 1000].
Each element of arr is in the range [1, 1,000,000].
k is in the range [1, 1000].

Output
Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

Example 1
n = 3
k = 2
arr = [5, 3, 1]
output = [1, 5, 3]

We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

Example 2
n = 5
k = 3
arr = [8, 9, 11, 2, 1]
output = [2, 8, 9, 11, 1]
We can swap [11, 2], followed by [9, 2], then [8, 2].

Greedy Algorithm to Find Smallest Array after K Element Swapping

We can use greedy algorithm to solve this problem. Every iteration, we find the smallest element and try to move it to the front. Then if we stil can do element swapping after this, we can continue solving a smaller array.

Please note, when we get the smallest element in the unsorted array, we have to consider the K value as well, – as our target is to replace the current element in the front and there is no point to find a smallest element that is more than K steps away.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> findMinArray(const vector<int> &arr, int k) {
  vector<int> res(arr);
  for (int i = 0; (i < res.size()) && (k > 0); ++ i) {
    int curIdx = i;
    int kk = k;
    // find current smallest element after at most k swaps
    for (int j = i + 1; (j < res.size()) && (kk > 0); ++ j, --kk) {
      if (res[j] <= res[curIdx]) {
        curIdx = j;        
      }
    }
    // then swap it to the front if possible
    for (int j = curIdx; (j > i) && (k > 0); --j, --k) {
      swap(res[j], res[j - 1]);
    }
  }
  return res;
}
vector<int> findMinArray(const vector<int> &arr, int k) {
  vector<int> res(arr);
  for (int i = 0; (i < res.size()) && (k > 0); ++ i) {
    int curIdx = i;
    int kk = k;
    // find current smallest element after at most k swaps
    for (int j = i + 1; (j < res.size()) && (kk > 0); ++ j, --kk) {
      if (res[j] <= res[curIdx]) {
        curIdx = j;        
      }
    }
    // then swap it to the front if possible
    for (int j = curIdx; (j > i) && (k > 0); --j, --k) {
      swap(res[j], res[j - 1]);
    }
  }
  return res;
}

The time complexity is O(N^2).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Recursive Depth First Search Algorithm to Delete Leaves With a G  Algorithms to Determine a Palindrome Number  Algorithm to Compute the Fraction to Recurring Decimal of the Tw  Algorithms to Check if Array Contains Duplicate Elements  Recursive Depth First Search Algorithm to Compute the Sum of Nod  How to Convert Integer to the Sum of Two No-Zero Integers?  Algorithm to Generate the Spiral Matrix in Clock-wise Order  How to Remove the Duplicates from Sorted List (Leaving Only Dist  How to Sort a Linked List by Converting to Array/Vector?  Know The Effective and Smart SEO Reporting Tool You Must Use 
评论列表
添加评论