8.23 数组的partition调整

题目】:

  给定一个有序数组arr,调整arr使得这个数组的左半部分没有重复元素且升序,而不用保证右部分是否有序

  例如:

    arr=[1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9],调整之后arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, ...]

补充题目】:

  给定一个数组arr,其中只可能含有0、1、2三个值,请实现arr的排序

  另一种问法为:有一个数组,其中只有红球、篮球和黄球,请实现红球全放在数组的左边,篮球放在中间,黄球放在右边

  另一种问法为:有一个数组,再给定一个值k,请实现比k小的数都放在数组的左边,等于k的数都放在数组的中间,比k大的数都放在数组的右边

要求】:

  1、所有题目实现的时间复杂度为O(N)

  2、所有题目实现的额外空间复杂度为O(1)

题目来源:左程云老师《程序员代码面试指南》

原文地址:https://www.cnblogs.com/latup/p/10204828.html

时间: 01-01

8.23 数组的partition调整的相关文章

[算法]数组的partition调整

题目一: 给定一个有序数组arr,调整arr使得这个数组的左半部分没有重复部分且升序,而不用保证右部分是否有序. 例如:arr=[1,2,2,2,3,3,4,5,6,6,7,7,8,8,9,9],调整之后arr=[1,2,3,4,5,6,7,8,9-]. 要求: 时间复杂度O(N),额外空间复杂度O(1) 程序: public static void leftUnique(int[] arr) { if (arr == null || arr.length < 2) { return; } in

PHP 23 - 数组array_fill-array_fileter-array_flip-array_key_exists-array_keys

array_fill()通过指定的索引顺序及个数生成数组. array_fileter数组过滤函数,通过回调函数的方式返回新数组,如果回调函数返回true, 数组元素返回到新数组当中. array_flip()把数组中的键名与键值进行交换,如果调换名键名相同,那么就后面的覆盖前面的. array_key_exists判断内容是否是数组的键名. array_keys()返回数组中所有的键名.

关于Delphi中二维数组的声明和大小调整(对非基本类型数据,小心内存泄漏)

这是一个实例: procedure TMainForm.Button1Click(Sender: TObject);var  arr:array of array of string;begin  setlength(arr,2,3);  arr[1,2]:='this is a test';  setlength(arr,0,0);  setlength(arr,4,5);  showmessage(arr[1,2]); end; 声明一个二维数组的方法是用 array of array of

numpy 多维数组的存取

多维数组的存取和一维数组类似,由于多维数组有多个轴,所以他的下标需要多个值来表示.这里讨论的主要是二维数组.二维数组0轴以行为单位,1轴以列为单位,存取数组使用元组作为下标,需要注意的是,python中的元组通常用圆括号括起来,但是其实元组的语法只需要用逗号隔开就可以.因此a[1,2]等价a[(1,2)].如果下标元组只包含整数的切片,那么得到的数组和原始数组共享数据,改变得到的数组就会改变原始数组的数据. >>> x array([[ 0, 1, 2, 3, 4, 5], [ 6, 7

C语言实现数组快速排序(含对算法的详细解释)

/* 说明: 代码参考过网上代码,但分析为个人原创,本贴重在说明快速排序算法的思想和运行过程. */ 代码部分: #include<stdio.h> #include<stdlib.h> void quickSort(int* arr,int startPos, int endPos) { int i, j; int key; key = arr[startPos]; i = startPos; j = endPos; while (i<j) { while (arr[j]

【Atheros】网卡驱动速率调整算法概述

我做网卡驱动,最主要的内容就是设计和改进速率调整算法,随着802.11协议簇的新标准越来越多,速率越来越高,调制编码方式也越来越多,一般来说,速率越高越可能丢包,速率越低越稳定,这是整体状况,但不是必然的规律,所以,只用固定的速率来发送显然是不合适的,这就需要速率调整算法来自己调节,信号比较好的时候,就用高速率来发送,信道状况不好了,就换用低速率来发,atheros驱动中提供了两种可选的速率调整算法,ath9k和minstrel,其中minstrel要好一些,后面我会分别根据源码解读minstr

常用排序算法简介以及Java实现代码

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序. 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的. 冒泡,插入,基数,归并属于稳定排序 选择,快速,希尔,堆

排序算法(java版)

1. 冒泡算法2. 快速排序3. 归并排序4. 选择排序5. 堆排序 排序算法 重要性不言而喻,很多算法问题往往选择一个好的排序算法往往问题可以迎刃而解 1.冒泡算法 冒泡排序(Bubble Sort)也是一种简单直观的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端.也就是双重循环就可以搞定的问题但是需要注意下一

数据结构总结

剑指OfferJAVA版 1.      排序算法 稳定性的概念: 假定待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,称这种排序算法是稳定的,否则称为不稳定的. package com.ljl.sort; import org.junit.Test; /** * 七大排序算法 * @author acer * */ public class Sort { private int[] unsorted={1,3,2,8,9,7,6,6,5,3,4};

TJI读书笔记15-持有对象

body, td { font-family: 微软雅黑; font-size: 10pt; } TJI读书笔记15-持有对象 总览 类型安全和泛型 Collection接口 添加元素 List 迭代器 LinkedList 栈 Set Map Queue Collection和Iterator Foreach与迭代器 总结 总览 It's a fairly simple program that only has a fixed quantity of objects with known l