Greedy Algorithm to Find the Lexicographically Smallest Sequence

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

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) —

推荐阅读:
“暖阳”社会实践队调研组对调研结果做出总结  Switching to a Blogging Career: Can You Afford to Work from Home  4 Features that Will Enhance Your Blog  Amazon Surpasses Google: Should you Change your SEO Strategies?  How to Optimize WordPress Categories and Tags  Blogging Royalties: Michelle Obama Interviewing Barack on her Po  Content Marketing: Expectations Vs Reality  Blogger Skills: LinkedIn and Microsoft’s Digital Skill Programs   5 Tips for Creating a Content Strategy for Your eCommerce Websit  5 Tips You Can Use to Launch a Successful Property Management Bl 
评论列表
添加评论