数组中重复的数字、二维数组中的查找、替换空格--Java知识点解析

数组中重复的数字、二维数组中的查找、替换空格--Java知识点解析

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:

{2, 3, 1, 0, 2, 5}

Output:

2

1)任意一个重复的数字，所以当查找到第一个重复的时候就可以return

2)如果要求时间复杂度O(N)，空间复杂度O(1)。则不能使用排序算法。如果没有要求，可以先进行排序，扫描排序之后的数组即可。

3)解决思路一：采用将值为i的元素调整到第i个位置，如果发现位置上面的元素已经有对应数值了，则发现有重复。先进行交换，将所有数字放入对应的位置，交换前面加上一个判断，如果你发现对应位置的数字是对的，然后你又发现一个这样的数字，那这个数字就是重复的一个数字。如果发现多个，那将重复的数字放在数组中进行保存。

解决思路二：哈希表。从头到尾扫描数组，每扫描到一个数字，判断该数字是否在哈希表中，如果该哈希表还没有这个数字，那么加入哈希表，如果已经存在，则返回该数字；时间复杂度：O(n)，空间复杂度:O(n)

解决思路三：排序，再遍历

交换数字，按位置比较。

public class repeatNum3 {

/**

* @param ycy

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] num= {2,3,1,0,2,5};

int repeat = 0;

int j = 0;

if(num == null || num.length<=0){

System.out.println("不存在重复的数据");

}

System.out.println("数据长度"+num.length);

for(int i=0;i

while(num[i] != i){

if(num[i] == num[num[i]]){

repeat = num[i];

System.out.println("存在重复的数据"+repeat);

return;

}

swap(num,i,num[i]);

}

}

return;

}

public static void swap(int[] num,int i,int j){

int t = num[i];

num[i] = num[j];

num[j] = t;

}

}

各种排序算法比较

各种常用排序算法

类别

排序方法

时间复杂度

空间复杂度

稳定性

复杂性

特点

最好

平均

最坏

辅助存储

简单

插入

排序

直接插入

O(N)

O(N2)

O(N2)

O(1)

稳定

简单

希尔排序

O(N)

O(N1.3)

O(N2)

O(1)

不稳定

复杂

选择

排序

直接选择

O(N)

O(N2)

O(N2)

O(1)

不稳定

堆排序

O(N*log2N)

O(N*log2N)

O(N*log2N)

O(1)

不稳定

复杂

交换

排序

冒泡排序

O(N)

O(N2)

O(N2)

O(1)

稳定

简单

1、冒泡排序是一种用时间换空间的排序方法，n小时好

2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级

3、最好的情况是数据本来就有序，复杂度为O(n)

快速排序

O(N*log2N)

O(N*log2N)

O(N2)

O(log2n)~O(n)

不稳定

复杂

1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。

2、划分之后一边是一个，一边是n-1个，

这种极端情况的时间复杂度就是O(N^2)

3、最好的情况是每次都能均匀的划分序列，O(N*log2N)

归并排序

O(N*log2N)

O(N*log2N)

O(N*log2N)

O(n)

稳定

复杂

1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。

基数排序

O(d(r+n))

O(d(r+n))

O(d(r+n))

O(rd+n)

稳定

复杂

注：r代表关键字基数，d代表长度，n代表关键字个数

2、二维数组中的查找

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

Consider the following matrix:

[

[1, 4, 7, 11, 15],

[2, 5, 8, 12, 19],

[3, 6, 9, 16, 22],

[10, 13, 14, 17, 24],

[18, 21, 23, 26, 30]

]

Given target = 5, return true.

Given target = 20, return false.

解题思路

1 )二维数组是一个有序数组，其任意一个数是大于他左边的数，小于其下边的数。所以可以从右上角进行比较，然后根据target与当前元素的大小关系进行对应的位置范围缩小。

2 )如果等于当前比较元素则直接进行返回，如果大于当前元素则下移一行，如果小于小于当前元素，则左移一列。

剑指offer通过的代码：

public class Solution {

public boolean Find(int target, int [][] array) {

boolean result = false;

System.out.println(" "+array.length+" "+array[0].length);

if(array.length==0 || array[0].length==0 )

return result;

int i=array.length-1,j=0;

while(j0)

{

if(target>array[i][j])

j++;

if(target

i--;

if(target == array[i][j])

return true;

}

return false;

}

}

本地编码：

public class SearchNum4 {

/**

* @param ycy

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

int[][] matrix = {

{1,   4,  7, 11, 15},{2,   5,  8, 12, 19},{3,   6,  9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};

int target1 = 5;

int target2 = 19;

if(matrix == null || matrix.length == 0|| matrix[0].length == 0){

System.out.print("二维数组无数据");

}else{

int row = matrix.length,cols = matrix[0].length;

int i = 0,j = cols-1;  //右上角的位置

while(i<= row -1 && j>= 0){

if(target2 == matrix[i][j]){

System.out.println("存在");

return;

}else if(target2 > matrix[i][j] ){

i++;

}else{

j--;

}

}

System.out.println("不存在");

}

return;

}

}

3 、替换空格

将一个字符串中的空格替换成 "%20"。

Input:

"A B"

Output:

"A%20B"

解题思路

1)将字符串通过 A=input.toCharArray(); 转换为字符数组，如果非空格则直接进行字符相加，如果是空格，则加“%20”。最终得到新的字符串，原来的字符数组长度没有变化，只是产生一个转换后的字符串；

2)因为空格要替换为三个字符%20，所以遍历到空格的时候，在尾部填充两个空格，然后原来的末尾元素填充到新的末尾，然后前面空格部分逆向填充%20；

剑指offer通过的代码为：

public class Solution {

public String replaceSpace(StringBuffer str) {

StringBuffer result = new StringBuffer();

for(int i=0;i

{

if(str.charAt(i) == ' ')

result = result.append( "%20");

else

result = result.append(str.charAt(i));

}

return result.toString();

}

}

解决思路一：字符串转换为字符数组，赋值新字符串的方法

import java.util.Arrays;

public class replaceSpace5 {

/**

* @param ycy

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

String input = "A B B ";

String replace = "%20";

String newString = "";

char[] A;

A=input.toCharArray();  //将字符串转换为字符数组

for(int i=0;i

//System.out.println(input.charAt(i));

if(' '== A[i]){

A[i] = '%';

newString = newString + "%20";

System.out.println("当前字符串： "+newString);

}else{

newString = newString+A[i];

}

}

System.out.println("最终字符串： "+newString);

System.out.print("A字符串:");

for(int i=0;i

System.out.print(A[i]);

}

return;

}

}

解决思路二：扩充字符长度，逆序插入

将String转换成StringBuffer

方式一：利用构造函数

String str=“Hello World.”;

StringBuffer buffer = new StringBuffer(str);

方式二：调用append函数

String str=“Hello World.”;

StringBuffer buffer = new StringBuffer();

buffer.append(str);

实现代码：

public class replaceSpace53 {

/**

* @param ycy

*/

public static String replace(StringBuffer sbf){

int p1 = sbf.length()-1;

for(int i=0;i<=p1;i++){   //此处是i<=p1，不是i

if(sbf.charAt(i)==' '){

sbf.append("  ");

}

}

int p2 = sbf.length()-1;

while(p1>=0 && p2>p1){

char c = sbf.charAt(p1--);

if(c==' '){  //倒叙插入

sbf.setCharAt(p2--, '0');

sbf.setCharAt(p2--, '2');

sbf.setCharAt(p2--, '%');

}else{

sbf.setCharAt(p2--, c);

}

}

return sbf.toString();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

String input = "A B B ";

String replace = "%20";

StringBuffer sb = new StringBuffer(input);  //将String转换成StringBuffer

String newString = replace(sb);

System.out.print(newString);

}

}

1)String

String类是final类，也即意味着String类不能被继承，并且它的成员方法都默认为final方法。在Java中，被final修饰的类是不允许被继承的，并且该类中的成员方法都默认为final方法。在早期的JVM实现版本中，被final修饰的方法会被转为内嵌调用以提升执行效率。而从Java SE5/6开始，就渐渐摈弃这种方式了。因此在现在的Java SE版本中，不需要考虑用final去提升方法调用效率。只有在确定不想让该方法被覆盖时，才将方法设置为final。

2) StringBuffer的常用方法解析

StringBuffer a=new StringBuffer()

1     public StringBuffer append(String s)；

将指定的字符串追加到此字符序列。

2     public StringBuffer reverse()

将此字符序列用其反转形式取代。

3     public insert(int offset, int i)

将 int 参数的字符串表示形式插入此序列中。

4     replace(int start, int end, String str)

使用给定 String 中的字符替换此序列的子字符串中的字符。

3)三者的区别

String为字符串常量，而StringBuilder和StringBuffer均为字符串变量，即String对象一旦创建之后该对象是不可更改的，但后两者的对象是变量，是可以更改的。

String：适用于少量的字符串操作的情况

StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况，非线程安全

StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况，线程安全的

对于StringBuffer转化为String可使用 String b=a.toString()，对于String转为StringBuffer可使用StringBuffer b=new StringBuffer(string)

扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！

数组中重复的数字、二维数组中的查找、替换空格--Java知识点解析相关教程