Vyxal 3, 16 bytes

L:ɾẋΩᵛC₌}ƛ?ÞṅL}g

Simple bruteforce, probably can be golfed more.

Try it Online!

L:ɾẋΩᵛC₌}ƛ?ÞṅL}g­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁡‏⁠⁠⁠⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏⁠⁠⁠⁠⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌­
L:ɾẋ              # ‎⁡Nth cartesian power of range [1, length]
    Ω   }         # ‎⁢Filter by items where
     ᵛC₌          # ‎⁣Count of each item is item
         ƛ    }   # ‎⁤Map through list
          ?ÞṅL    # ‎⁢⁡Length of multiset difference between input and item
               g  # ‎⁢⁢Push minimum
💎

Created with the help of Luminespire.

R, 88 bytes

\(x,n=sum(x|1))min(combn(rep(1:n,n),n,\(r)`if`(all(names(t<-table(r))==t),sum(r!=x),n)))

Attempt This Online!

Haskell + hgl, 28 bytes

mMl<df**<fb(jn rl)<<dpS uq<l

I didn't want to brute force this, so I didn't. Although brute forcing would probably be shorter.

Explanation

First we find all the strictly descending integer partitions of the length of the input. We convert these to "perfect lists". This gives us all the perfect lists with the same size as the input. Then we take use the set difference to remove the elements in the input from each perfect list, these represent the number of replacements that need to be done. Then we get the size of the smallest element and output that.

Reflection

This answer feels painfully long. There are a couple things here:

• dpS uq is a bad way to get strictly descending integer partitions. It is 6 bytes long and slower than it needs to be. There should be a 3-byte version.
• This isn't the first time I've wanted a function that zips and then concatenates, but I apparently haven't added it. It would be useful here.
• There should be a shorter way to replicate every item in a list its own number of times (currently fb(jn rl)). I remember noticing that some obscure combination of functions did this, but I can't remember which. It's really bothering me.

Jelly, 12 bytes

JṗLċⱮ`ƑƇn⁸§Ṃ

A monadic Link that accepts a list of integers and yields the minimal number to alter to form a perfect array.

Try it online! Or see the test-suite.

How?

Constructs all lists of the same length as the input using an alphabet of 1 through to that length (with the elements in all possible orders). Filters these down to perfect arrays. Counts the differing entries of each with respect to the input (by summing the results of a vectorised not-equal). Returns the minimum.

JṗLċⱮ`ƑƇn⁸§Ṃ - Link: list of integers, Array
J            - indices {Array} -> [1..length(Array)]
  L          - length {Array}
 ṗ           - {Indices} Cartesian power {Length}
                 -> all arrays of length length(Array) formed from 1..length(Array)
       Ƈ     - keep those for which:
      Ƒ      -   is invariant under?:
    Ɱ`       -     map across itself with:
   ċ         -       count occurrences
        n⁸   - {that} not-equal? (vectorises) {Array}
          §  - sums
           Ṃ - minimum

K (ngn/k), 29 bytes

{&/+/~x=+{+/x=\:x}/'+!#/2##x}

Try it online!

+!#/2##x Generate all n-tuples with values in [0,n), where n is the length of the input.
{...}/' For each tuple, run until convergence:
+/x=\:x ... Replace each value with its count.¹
~x=+ element-wise comparison between the input and each generated tuple.
&/+/ Find the minimum number of different values.

¹ If this converges it must have reached a perfect array. Right now I can't think of a proof that it always converges (or equivalently, there are no cycles of length >1).

05AB1E, 13 bytes

ā¤ãʒТQ}€-ĀOß

Port of @mathScat's Vyxal answer.

Try it online or verify all test cases.

Explanation:

ā          # Push a list in the range [1, (implicit) inpu-length]
 ¤         # Push its last item (without popping): the length
  ã        # Cartesian power, to create all possible lists of this length
   ʒ       # Filter it by:
    Ð      #  Triplicate the current list
     ¢     #  Pop two, and count how many times each item occurs
      Q    #  Check that this list of counts and current list are still the same
   }€      # After the filter: map over each remaining list:
     -     #  Subtract the values at the same positions from the (implicit) input-list
      Ā    # Check for each difference that it's NOT 0 (0 if 0; 1 otherwise)
       O   # Sum the checks of each inner list together
        ß  # Pop and push the minimum
           # (which is output implicitly as result)

Python3, 742 bytes

Rather long, but non-brute force solution (for the sake of variety)

from itertools import*
D=lambda d,n,K,U:{**{a:b for a in d if(b:=[j for j in d[a]if j not in K])},n:[*K,*U]}
def P(n,d,r,F):
 U=d.get(n,[])
 d={i:d[i]for i in d if i!=n}
 k=[[],[]]
 for i in d:
  if i<n or len(d[i])!=i:k[i>F]+=d[i]
 if len(k[1])>=r:yield D(d,n,K:=k[1][:r],U),K;return
 for K in combinations(k[0]+k[1],r):
  if[]==k[1]or any(j in K for j in k[1]):yield D(d,n,K,U),K
def f(a):
 d,I={},0
 for i in a:d[i]=d.get(i,[])+[I];I+=1
 q=[(len(a),len(a),d,0)]
 M=-1
 while q:
  n,A,d,C=q.pop(0)
  if all(i==len(d[i])for i in d):M=min(M,C)if M!=-1 else C;continue
  if n==0:continue;
  if len(L:=d.get(n,[]))!=n:
   r,F=n-len(L),A-n
   for u,i in P(n,d,r,F):
    if M==-1 or C+len(i)<M:q+=[(F,A-n,u,C+len(i))]
  q+=[(n-1,A,d,C)]
 return M

Try it online! (includes extra/longer test cases)

Charcoal, 33 bytes

Ｉ⌊ＥΦＥＸ²Ｌθ⌕Ａ⮌⍘⊗ι²1⁼ΣιＬθΣＥι⌈⟦⁰⁻λ№θλ

Try it online! Link is to verbose version of code. Explanation:

ＥＸ²Ｌθ⌕Ａ⮌⍘⊗ι²1

Generate all subsets of {1..l}, where l is the length of the input array.

Φ....⁼ΣιＬθ

Filter for those that sum to l.

Ｉ⌊Ｅ...ΣＥι⌈⟦⁰⁻λ№θλ

Calculate the number of changes required for each subset and output the minimum.

JavaScript (ES7), 122 bytes

Brute force.

a=>eval("for(m=s=a.length,n=s**s;n--;)a.map(c=(x,i)=>(c[v=n/s**i%s+1|0]=-~c[v],d+=v!=x,v),d=0).some(v=>c[v]-v)|d>m?m:m=d")

Try it online!

Commented

This is a version without eval() for readability.

a => {                  // a[] = input array
  for(                  // main loop:
    m =                 //   m = minimum score
    s = a.length,       //   s = size of a[]
    n = s ** s;         //   n = counter, initialized to s ** s
    n--;                //   decrement n down to 0
  )                     //
    a.map(c =           // c = object to count value occurrences
    (x, i) =>           // for each element x at index i in a[]:
      ( c[              //   increment c[v]
          v =           //   where v is:
            n / s ** i  //     a value in [1 .. s] computed
            % s + 1 | 0 //     according to n and i
        ] = -~c[v],     //
        d += v != x,    //   increment d if v != x
        v               //   yield v
      ),                //
      d = 0             //   start with d = 0
    )                   // end of map()
    .some(v =>          // for each value v in the result of map():
      c[v] - v          //   trigger some() if c[v] != v
    ) |                 // end of some()
    d > m ?             // if some() was triggered or d > m:
      m                 //   do nothing
    :                   // else:
      m = d;            //   update m to d
  return m              // return m
}                       //

APL (Dyalog Classic), 39 37 bytes

{⌊/+/¨⍵∘≠¨{⍵/⍨{⊃∧⌿{⍺=⍴⍵}⌸⍵}¨⍵},⍳⍴⍨⍴⍵}

Try it online!

{⌊/+/¨⍵∘≠¨{⍵/⍨{⊃∧⌿{⍺=⍴⍵}⌸⍵}¨⍵},⍳⍴⍨⍴⍵}
{                               ,⍳⍴⍨⍴⍵} generate all n-length arrays of numbers 1-n (where n is the input length)
          {⍵/⍨              ¨⍵}        keep only arrays for which
              {⊃∧⌿{⍺=⍴⍵}⌸⍵}           all numbers appear a number of times equal to their value (perfect arrays)
      ⍵∘≠¨                              for each, find the number of elements that differ from the input
 ⌊/+/¨                                  and return the minimum

Wolfram Language(Mathematica), 119 88 bytes

Saved 31 bytes thanks to @ZaMoC

88 bytes version. Try it online!

m@a_:=Min[a~HammingDistance~#&/@Select[Range[n=Tr[1^a]]~Tuples~n,And@@SameQ@@@Tally@#&]]

119 bytes version. Try it online!

f@a_:=AllTrue[Tally@a,#[[2]]==#[[1]]&]
m@a_:=With[{n=Length@a},Min[HammingDistance[a,#]&/@Select[Tuples[Range@n,n],f]]]

Ungolfed version. Try it online!

IsPerfectArray[arr_] := 
  AllTrue[Tally[arr], #[[2]] == #[[1]] || #[[2]] == 0 &];
MinChangesToPerfectArray[arr_] := 
  Module[{n = Length[arr], perms, perfectArrays, changeCounts}, 
   perms = Tuples[Range[n], n];
   perfectArrays = Select[perms, IsPerfectArray];
   changeCounts = HammingDistance[arr, #] & /@ perfectArrays;
   Min[changeCounts]];

(*Test cases*)
Print[MinChangesToPerfectArray[{0}]];
Print[MinChangesToPerfectArray[{1, 2, 3}]];
Print[MinChangesToPerfectArray[{5, 5, 5, 5, 5}]];
Print[MinChangesToPerfectArray[{23, 7, 4, 8}]];
Print[MinChangesToPerfectArray[{100 , 100 , 100 , 6}]];
Print[MinChangesToPerfectArray[{5, 5, 5, 5, 5, 5}]];

Python 3 - 157 Bytes

This is a brute force solution. It won't always run fast, but it gets the job done nicely.

lambda l:(N:=len(l))-max([sum([l[p]==k[p]for p in range(N)])for k in[[i//(N**j)%N+1for j in range(N)]for i in range(N**N)]if all([g==k.count(g)for g in k])])

Try it online!

Explanation

(lambda l:                            #Define a function that takes a list l
    (N:=len(l))-                      #Return N (the length of l) minus the following
    max([                             #The maximum value in this list
        sum([                         #Sum the True values in this list
            l[p]==k[p]                #p-th item in the input equals item in k
            for p in range(N)         #Where p is the p-th item in the lists
        ])
        for k in                      #Loop through the items in this list; k equals the item
        [
            [
                i//(N**j)%N+1         #Goes through all possible arrays with max N and length N
                for j in range(N)     #j is equal to 1,2...N
            ]
            for i in range(N**N)      #Do this for i = 1,2...N**N to get all possible lists
        ]
        if all([                      #Only include the list if all of these Booleans are true
            g==k.count(g)             #Is g equal to how many times g occurs?
            for g in k                #Do this for every item in all possible lists
        ])
    ])
)

JavaScript (Node.js), 112 bytes

f=(z,a=[],i=0)=>1/z[i]?Math.min(...z.map((_,j)=>(++j!=z[i])+f(z,t=[...a],i+1,t[j]=-~t[j]))):a.some((v,i)=>v-i)*i

Try it online!

Recursive is bit shorter

Python, 111 bytes

f=lambda L,l=0,p=0,s=0:(d:=len(L)-p)and min(f(L,k,p+k,s+max(0,k-L.count(k)))for k in[*range(-~l,-~d//2),d])or s

Attempt This Online!

obsolete Python, 128 bytes

f=lambda L,*s:[r:=len(L)-sum(s)]and min([f(L,*s,k)for k in range([0,*s][-1]+1,-~r//2)]+[sum(max(0,t-L.count(t))for t in[*s,r])])

Attempt This Online!

How?

• Creates all strictly increasing partitions of the length of the input.
• For each partition:
  • Counts how many instances of each element are in the list and
  • if there are too few adds the number missing to the tally for that partition
• Takes the minimum over all sums.

Desmos, 123 bytes

f(l)=[sgn([B[B=j].count-jforj=B]^2.max)L+sgn(B-l)^2.totalfori=[0...L^L]].min
L=l.length
B=l[mod(floor(Li/L^{[1...L]}),L)+1]

Brute force. This theoretically works for any list, but in practice it errors out for input lists with greater than 5 elements because of Desmos's 10000 element restriction.

Try It On Desmos!

Try It On Desmos! - Prettified