Height Checker

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.

Notice that when a group of students is selected they can reorder in any possible way between themselves and the non seleted students remain on their seats.

---

Tips

Build the correct order of heights by sorting another array, then compare the two arrays.

---

Solution

1. my badly solution

like bubble sort

• get the smallest height index A
• swap A with current index
• mark the heights to map
• after sorting,get how many heights have swaped?

---

2. best solution

• Build the correct order of heights by sorting another array
• then compare the two arrays.

int heightChecker(vector<int> &heights)
{
    int res = 0;
    vector<int> sortHeights(heights.begin(), heights.end());
    sort(sortHeights.begin(), sortHeights.end());
    for (size_t i = 0; i < heights.size(); i++)
    {
        if (heights[i] != sortHeights[i])
        {
            res++;
        }
    }
    return res;
}

---