How about:

Let L be the length of your array. Then you want to find first the range of numbers that will minimize your convertions [Min,Max]. So:

1. calculate the histogram of your array IniArray.
2. calculate an array with the same length as your histogram which has the value 1 where the histogram bin is filled and 0 otherwise (I will call it Mask). This step can be computed almost directly without having to calculate the histogram in step (1); it is calculated the same way as the histogram but instead of adding +1 to the bins, just assign them the value '1'.
3. Calculate the Mean Filter of this array using a filter size of L. This can be done by first computing the cummulated array (Cummul) of the Maskand then taking differences

 MeanFilter[i] = (Cummul[min(i+L/2,L-1)] - Cummul[max(0,i+L/2-L-1)])/L

4. The index (I) of the maximum value in MeanFilter will give you the required range. [Min,Max]= [min(I+L/2,L-1) , max(0,I+L/2-L-1) ]. If the maximum value is repeated take any of their corresponding indexes.
5. Let Sbe the summatory of the values of Mask within the range [Min,Max], then the minimum number of operationsN is calculated as N=L-S

If the order doesn't matter, then the final array is just the sequence of integers from Min to Max. If you need the precise convertion operations and you want to maintain the initial array order as much as possible:

6. Create an array (Filled) of length 'L' and initialize all its values to a value outside the range [Min,Max]. This value NFV will be the reference value meaning "not yet filled".
7. for each element V in your initial array, calculate its index position in the histogram as J=V-Min. If J<0 or J>=L, do nothing for the moment. Otherwise, if Filled[J]==NFV, then set Filled[J]=V; else do nothing.
8. We repeat step 7 but this time we will store the changes: for each element IniArray[i]=V in your initial array, calculate its index position in the histogram as J=V-Min. If J<0 or J>=L or Filled[J]!=NFV, iterate throughout Filled until you find Filled[K]==NFV and then note down the change (IniArray[i]=V) => (K+Min) and update 'Filled[K]==K+Min`

Let A[0..N) be the sorted array. Two consecutive elements A[i-1] and A[i] have a gap if A[i-1] + 1 < A[i] (the size of the gap is A[i] - A[i-1] - 1 max 0).

A trivial but important observation is that in a minimal solution the elements that are converted belong to the left and/or right hand sides of the array.

More precisely, any minimal solution can be characterized as a partition A[0..L) A[L..N-R) A[N-R..N), for some L and R (0 ≤ L ≤ N-R ≤ N), where all the elements of A[0..L) and A[N-R..N) will be converted. No element of A[L..N-R) gets converted and any gaps it may contain are (afterwards) filled using the results of the left- and right hand side conversions (L+R in total) .

Define G(L,R) be the total size of the gaps in A[L..N-R), i.e. G(L,R) = (Σi: L < i < N-R : A[i] - A[i-1] - 1 max 0). Then (L,R) is a solution (not necessarily a minimal one) if G(L,R) ≤ L+R (since then there are enough converted numbers to fill all the gaps in A[L..N-R)). Furthermore, (L,R) is a minimal solution if L+R is minimal.

Hence the essence of the problem is to minimize L+R such that G(L,R) ≤ L+R.

G (or rather G(L,R)-L-R) is decreasing in both arguments, so this minimization problem can easily be solved in O(N) time & space.

Addendum: after rereading the question I noticed that duplicates are undesirable, so the minimization problem is not G(L,R) ≤ L+R, but rather G(L,R) ≤ L+R + D(L,R), where D(L,R) = the number of duplicates in [L..N-R). It hardly matters for the algorithm, but it does affect some of the wording above (since the remaining D(L,R) duplicates in the middle part do undergo conversion). An easier but less intuitive alternative is to define the gap size as as abs(A[i]-A[i-1]-1).

We can solve this with O(n log n) complexity by sorting the array, collapsing any duplicates into a single entry -- call this B. Then for each entry in B as a candidate for the lowest value, low, in the solution; we fix the highest value, high as low + input_length - 1. The cost for each such candidate is now the input length subtracted by the number of elements in B that are in the [low, high] range, which can be found in O(n) for the entire iteration by augmenting a pointer to the index for high as we iterate. (We might need to mirror for each candidate as the potential high as well.) Pick the lowest cost.

For example:

Input: 6 4 1 7 10

B:     1 4 6 7 10

Candidates:

[1, 5]  cost 5 - 2 = 3
[4, 8]  cost 5 - 3 = 2
[6, 10] cost 5 - 3 = 2
[7, 11] cost 5 - 2 = 3
...etc


Input: 1 4 4 4 4

B: 1 4

Candidates:

[1, 5] cost 5 - 2 = 3
...etc

I've got some good results with the algorithm below. See also the hand-crafted example and the Python implementation here.

Observations and Definitions

One way of summarising the task is: reduce gaps in a series of numbers to zero by renumbering as few numbers as possible.

Let's call a "run" a series of one or more consecutive integers like [45, 46, 47]. And a "gap" is one or more missing numbers in a list of integers.

E.g. [1, 2, 5, 6, 9, 11] contains:

• four runs [1, 2], [5, 6], [9] and [11]
• three gaps [3, 4], [7, 8] and [10]

Some observations (the hand-crafted example below may help to explain these better):

1. renumbering numbers off the runs at the end and the beginning is efficient. This is because when numbers in an "outer" run get renumbered, the run may be used up and disappear. When that happens, the gap next to it disappears too.

2. Moving "outer" numbers so they fill gaps in the middle has a chance of (a) eliminating a gap at the outer edge (b) eliminating a gap in the middle (c) increasing the length of a run. For example, renumbering [11] to 9 removes the [10] gap and increases the length of the [9] run but in this case reduces the size of, but does not eliminate, a gap in the middle. Both removing a gap (or gaps) and increasing the length of an existing run means there are more consecutive numbers and that we're making progress

3. conversely, renumbering a number near the middle of the list is not likely to be as efficient. At best, if the number has gaps on both sides then it is 2/3 as effective as renumbering an outer number, because it can never remove an outer gap

4. each number may be renumbered more than once during the process, but all we need is one renumber from initial value to final value. This gives us an opportunity to optimise

Some of the above observations are more probabilities than certainties, but a good strategy appears to be "renumber from the outside in."

Algorithm

1. sort the list of numbers into ascending order so you can see where the runs and gaps are
2. take the last run of consecutive numbers (e.g. [98, 99, 100]) or the first run of consecutive numbers (e.g. [1, 2]), whichever has the fewest numbers. In this case [1, 2] would be picked because it has only 2 elements. If the first and last runs are of the same length, choose either
3. take numbers from the last/first run and squeeze as many as possible into the gap that's nearest the middle
4. repeat from 2 until there are no more gaps
5. optimise renumbers-- see below.

This Python implementation uses the above algorithm. There's no guarantee that its solutions are optimal but the renumber counts are reassuringly low for small cases I've looked at closely. It solves for 5000 numbers and over 1000 gaps in a few seconds (test data in source) and the minimal number of moves is subjectively about right.

$ python continuous.py
Original numbers: [1, 2, 5, 6, 9, 10, 13, 14, 19]
19 -> 3
14 -> 4
13 -> 7
10 -> 8
(4 renumbers)
Original order with renumbers:
[1, 2, 5, 6, 9, 8, 7, 4, 3]
Gaps in final output (check=0): 0
Sorted:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
no of integers in original: 9

Hand-crafted Example

Take the numbers [1, ..., 3, ..., 5, 6, ..., 9, 10, 11, ..., 13, ..., 19]:

The [7, 8] gap is nearest the middle (3rd gap of 5); The run [1] (1 number) is the same size as run [19] (1 number) so 1 is arbitrarily chosen from the first run and renumbers as 7. The [7, 8] gap is now reduced to [8]; because 1 has been renumbered, there is no longer a [2] gap either, as the sequence now starts from the number 3:

[1, 3, 5, 6, 9, 10, 11, 13, 19] -> [*x,* 3, 5, 6, *7,* 9, 10, 11, 13, 19]

(x is where the original number was before renumbering.)

The [8] gap is nearest the middle (2nd gap of 3); 3 peels off from the start and renumbers as 8, removing the [8] gap and the [4] gap:

[3, 5, 6, 7, 9, 10, 11, 13, 19] -> [*x,* 5, 6, 7, *8,* 9, 10, 11, 13, 19]

The [12] gap is nearest the middle-- or as near the middle as the [14..18] gap; [19] is shorter than [5..7] so the last run, [19] is renumbered first. The number 19 renumbers as 12, plugging the 12 gap and removing the [14..18] gap:

[5, 6, 7, 8, 9, 10, 11, 13, 19] -> [5, 6, 7, 8, 9, 10, 11, *12,* 13, *x*]

Because there are no more gaps, we have an unbroken sequence of numbers [5..13].

The answer is how many numbers you have moved:

1 -> 7, 3 -> 8, 19 -> 12 (3 moves)

Optimising Renumbers

What if the [14, 15, 16, 17, 18] gap had been chosen as the middle gap instead of the [12] gap? In that case we'd get two renumbers: 19 -> 14 followed by 14 -> 12.

You can optimise the answer further by collapsing redundant renumbers if there are any. As per observation 4, no number needs changing more than once, so 19 -> 14 followed by 14 -> 12 is equivalent to 19 -> 12. If you have two or more renumbers that are chained like this, they can be replaced by one renumber.

As a further example, the sequence [1, 3, 5, 7, 9] could be consolidated using the following renumbers:

9 -> 6, 7 -> 2, 6 -> 4

This can be reduced to:

9 -> 4, 7 -> 2

giving the continuous run [1, 2, 3, 4, 5] in 2 moves rather than 3.