我有一个由 n 个整数组成的数组，我需要将其中的任何元素除以 2（返回结果的上限）k 次，以便总和最小。与 n 相比，k 的值可能非常大。
我正在使用此代码：
private static int GetMaxSum(int[] array, int k)
{
int n = array.Length;
for (int i = 0; i < k; i++)
{
var indexAtMax = GetMaxIndex(array);
if (array[indexAtMax] == 1) break;
array[indexAtMax] = array[indexAtMax] / 2 + array[indexAtMax] % 2;
}
return array.Sum();
}
private static int GetMaxIndex(int[] array)
{
int maxIndex = 0;
int max = array[0];
for (int i=1; i<array.Length;i++)
{
if (array[i] > max)
{
max = array[i];
maxIndex = i;
}
}
return maxIndex;
}
我们如何通过使用最大堆或其他一些数据结构来进一步提高性能？
由于假设是 k>>n，更简单的算法的阶数为 O(kn)，这可能需要太多的迭代。我写了这段代码，考虑了这个问题，以及如何限制排序或计算最小值/最大值。我已经将数组划分为子数组，以便可以在子数组上执行操作而无需考虑操作顺序。
private static int GetMinSum(int[] array, int k)
{
int n = array.Length;
var sum = 0;
k = GetOptimizedListAndK(array, n, k, out var lists);
//If more sublists are needed
if (k > 0)
{
var count = lists.CountSum;
var key = lists.Key;
if (key > 0)
{
var poweroftwo = 1 << key;
sum += count * poweroftwo - k * poweroftwo / 2;
var dictionary2 = GetDictionary(array, lists, poweroftwo);
key = dictionary2.Keys.Last();
while (k > 0 && key > 0)
{
var list2 = dictionary2[key];
count = list2.Count;
if (k >= count)
{
list2.ForEach(
index => array[index] = array[index] / 2 + array[index] % 2);
dictionary2.Remove(key);
key = dictionary2.Keys.LastOrDefault();
k -= count;
}
else
{
if (k <= Log2(count))
{
for (int i = 0; i < k; i++)
{
var indexAtMax = GetMaxIndex(list2, array);
array[indexAtMax] = array[indexAtMax] / 2 + array[indexAtMax] % 2;
}
k = 0;
}
if (count - k <= Log2(count))
{
var minIndexes = GetMinIndexes(list2, array, count - k);
foreach (var i in list2)
{
if (!minIndexes.Contains(i))
{
array[i] = array[i] / 2 + array[i] % 2;
}
}
k = 0;
}
if (k > 0)
{
poweroftwo = 1 << key;
sum += list2.Count * poweroftwo - k * poweroftwo / 2;
dictionary2 = GetDictionary(array, list2, poweroftwo);
key = dictionary2.Keys.Last();
}
}
}
}
}
return array.Sum() + sum;
}
private static int GetOptimizedListAndK(int[] array, int n, int k, out Lists lists)
{
lists = null;
Dictionary<int, Lists> dictionary = new Dictionary<int, Lists>();
PopulatePowerBasedDictionary(array, n, dictionary);
var key = dictionary.Keys.Max();
while (key > 0 && k > 0)
{
lists = dictionary[key];
var count = lists.CountSum;
if (k >= count)
{
lists.ForEach(list => list.ForEach(index => array[index] = array[index] / 2 + array[index] % 2));
if (key > 1)
{
if (dictionary.TryGetValue(key - 1, out var lowerlists))
{
lowerlists.AddRange(lists);
lowerlists.CountSum += count;
}
else dictionary.Add((key - 1), lists);
}
dictionary.Remove(key);
key--;
k -= count;
}
else
{
if (k < Log2(count))
{
for (int i = 0; i < k; i++)
{
var indexAtMax = GetMaxIndex(lists, array);
array[indexAtMax] = array[indexAtMax] / 2 + array[indexAtMax] % 2;
}
k = 0;
}
if (count - k < Log2(count))
{
var minIndexes = GetMinIndexes(lists, array, count - k);
foreach (var list in lists)
{
foreach (var i in list)
{
if (!minIndexes.Contains(i))
{
array[i] = array[i] / 2 + array[i] % 2;
}
}
}
k = 0;
}
break;
}
}
return k;
}
private static void PopulatePowerBasedDictionary(int[] array, int n, Dictionary<int, Lists> dictionary)
{
for (int i = 0; i < n; i++)
{
if (array[i] < 2) continue;
var log2 = Log2(array[i]);
if (dictionary.TryGetValue(log2, out var lists))
{
lists[0].Add(i);
lists.CountSum++;
}
else
{
lists = new Lists(1,log2) { new List<int> { i } };
dictionary.Add(log2, lists);
}
}
}
private static int GetMaxIndex(List<int> list, int[] array)
{
var maxIndex = 0;
var max = 0;
foreach (var i in list)
{
if (array[i] > max)
{
maxIndex = i;
max = array[i];
}
}
return maxIndex;
}
private static SortedDictionary<int, List<int>> GetDictionary(int[] array, Lists lists, int poweroftwo)
{
SortedDictionary<int, List<int>> dictionary = new SortedDictionary<int, List<int>>();
foreach (var list in lists)
{
foreach (var i in list)
{
array[i] = array[i] - poweroftwo;
if (array[i] < 2)
{
continue;
}
var log2 = Log2(array[i]);
if (dictionary.TryGetValue(log2, out var list2))
{
list2.Add(i);
}
else
{
list2 = new List<int> { i };
dictionary.Add(log2, list2);
}
}
}
return dictionary;
}
private static SortedDictionary<int, List<int>> GetDictionary(int[] array, List<int> list, int poweroftwo)
{
SortedDictionary<int, List<int>> dictionary = new SortedDictionary<int, List<int>>();
foreach (var i in list)
{
array[i] = array[i] - poweroftwo;
if (array[i] < 2)
{
continue;
}
var log2 = Log2(array[i]);
if (dictionary.TryGetValue(log2, out var list2))
{
list2.Add(i);
}
else
{
list2 = new List<int> { i };
dictionary.Add(log2, list2);
}
}
return dictionary;
}
private static int GetMaxIndex(Lists lists, int[] array)
{
var maxIndex = 0;
var max = 0;
foreach (var list in lists)
{
foreach (var i in list)
{
if (array[i]>max)
{
maxIndex = i;
max = array[i];
}
}
}
return maxIndex;
}
private static HashSet<int> GetMinIndexes(Lists lists, int[] array, int k)
{
var mins = new HashSet<int>();
var minIndex = 0;
var min = int.MaxValue;
for (int j = 0; j < k; j++)
{
foreach (var list in lists)
{
foreach (var i in list)
{
if (array[i] < min && !mins.Contains(i))
{
minIndex = i;
min = array[i];
}
}
}
mins.Add(minIndex);
min = int.MaxValue;
}
return mins;
}
private static HashSet<int> GetMinIndexes(List<int> list, int[] array, int k)
{
var mins = new HashSet<int>();
var minIndex = 0;
var min = int.MaxValue;
for (int j = 0; j < k; j++)
{
foreach (var i in list)
{
if (array[i] < min && !mins.Contains(i))
{
minIndex = i;
min = array[i];
}
}
mins.Add(minIndex);
min = int.MaxValue;
}
return mins;
}
private static int Log2(int n)
{
return BitOperations.Log2((uint)n);
}
列表类：
public class Lists:List<List<int>>
{
public int Key { get; set; }
public int CountSum { get; set; }
public Lists(int countSum, int key):base()
{
CountSum = countSum;
Key = key;
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句