I'm not an engineer but a pilot, so I'll take a stab at answering.
There's no such thing as "50% less oxygen", the atmosphere will always be composed of 78% nitrogen, 21% oxygen, with the rest made up of CO2, argon, and other noble gases. That that said the density of oxygen decreases (oxygen molecules are further apart) with an increase in altitude, and as such an aircraft and engine's performance reduces.
A better way of explaining might be to look at the lift formula (lift = coefficient of lift x half of air density x speed² x wing surface area), as we know the force of lift opposes that of weight. With the value of air density in the formula decreasing, other values in the formula will have to increase in order to produce the required lift for a given aircraft weight. Increasing coefficient of lift can be achieved by increasing the camber of aerofoils, such as more slats or flaps. Increasing the takeoff speed would also work as you mentioned, however you're gonna need a loooooooooong runway to allow the plane/engine to accelerate, which is why high altitude airports such as Mexico City, Quito in Ecuador and Santiago in Chile feature longer than usual runways (might be challenging to produce a massive runway in mountainous terrain). Jet assisted takeoff bottles (or afterburners) could also help the aircraft accelerate to the required takeoff speed, but don't forget these bottles produce parasite drag (which will need to be overcome by additional thrust), and also increasing the weight of the aircraft (which is the problem we're trying to solve in the first place). The aircraft's wing could also be redesigned to increase the surface area.
I must admit the catapult idea might be a work around to increase a fighter jet's acceleration momentum, and thereby reaching the required takeoff speed at a shorter distance. I'm no structural engineer, but I'm pretty sure catapult aircraft require their landing gears (and perhaps other critical components?) to be reinforced to withstand the force of the catapult. So on top of installing catapults in high altitude air bases, the PLA's fleet assigned to the area will have to be overhauled? That sounds fairly expensive and inefficient. I've mentioned in a previous post, but perhaps a better work around to the problem might be to launch a fighter with it's required weapons loadout as well as sufficient contingent fuel, then have the fighter meet a tanker enroute to top up on gas before proceeding to their objective?