给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1]
输出:[0,1,2]
提示:
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶:
你能想出一个仅使用常数空间的一趟扫描算法吗?
var swamp = function(nums,i,j){
var temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
var sortColors = function(nums) {
var left = 0,right = nums.length - 1
var current = 0
while(current<=right){
if(nums[current]==0){
swamp(nums,current,left)
left++
current++
}else if(nums[current]==2){
swamp(nums,current,right)
right --
// current++
}else{
current++
}
// if(nums[current]==1){
// current++
// }
}
return nums
};
2、冒泡排序
var sortColors = function(nums) {
for(var i=0;i<nums.length-1;i++){
for(var j =i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
var temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
}
}
return nums
};
3、归并排序文章来源:https://www.toymoban.com/news/detail-652109.html
var sortColors = function(nums) {
mergeSort(nums, 0, nums.length - 1);
return nums
};
function mergeSort(nums, left, right) {
if (left < right) {
const mid = Math.floor((left + right) / 2);
mergeSort(nums, left, mid); // 对左半部分进行归并排序
mergeSort(nums, mid + 1, right); // 对右半部分进行归并排序
merge(nums, left, mid, right); // 合并两个排好序的子数组
}
}
function merge(nums, left, mid, right) {
const temp = new Array(right - left + 1);
let i = left;
let j = mid + 1;
let k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (let m = 0; m < temp.length; m++) {
nums[left + m] = temp[m];
}
}
// 4、快速排序文章来源地址https://www.toymoban.com/news/detail-652109.html
var sortColors = function(nums) {
quickSort(nums, 0, nums.length - 1);
return nums
};
function quickSort(nums,left,right){
if(left<right){
var l = left,r = right
var key = nums[l]
while(l<r){
while(l<r&&nums[r]>key){
r--
}
if(l<r){
nums[l++] = nums[r]
}
while(l<r&&nums[l]<key){
l++
}
if(l<r){
nums[r--] = nums[l]
}
}
nums[l] = key
quickSort(nums,left,l-1)
quickSort(nums,l+1,right)
// if(l-1>left){
// quickSort(nums,left,l-1)
// }
// if(l+1<right){
// quickSort(nums,l+1,right)
// }
}
}
到了这里,关于LeetCode 热题 100 JavaScript--75. 颜色分类的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!