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

「爱情、让人受尽委屈。」 2022-10-01 09:47 129阅读 0赞

## 1、数组中重复的数字 ##

## 题目描述 ##

在一个长度为 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)

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

交换数字，按位置比较。

> 1. public class repeatNum3 \{
> 2.     /\*\*
> 3.      \* @param ycy
> 4.      \*/
> 5.     public static void main(String\[\] args) \{
> 6.         // TODO Auto-generated method stub
> 7.         int\[\] num= \{2,3,1,0,2,5\};
> 8.         int repeat = 0;
> 9.         int j = 0;
> 10.         
> 11.         if(num == null || num.length<=0)\{
> 12.             System.out.println("不存在重复的数据");
> 13.         \}
> 14.         System.out.println("数据长度"+num.length);
> 15.         for(int i=0;i<num.length;i++)\{
> 16.             while(num\[i\] != i)\{
> 17.                 if(num\[i\] == num\[num\[i\]\])\{
> 18.                     repeat = num\[i\];
> 19.                     System.out.println("存在重复的数据"+repeat);
> 20.                     return;
> 21.                 \}
> 22.                     swap(num,i,num\[i\]);
> 23.             \}
> 24.         \}
> 25.         return;
> 26.     \}
> 27.     public static void swap(int\[\] num,int i,int j)\{
> 28.         int t = num\[i\];
> 29.         num\[i\] = num\[j\];
> 30.         num\[j\] = t;
> 31.     \}
> 32. \}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

### 各种排序算法比较 ###

<table> 
 <tbody> 
 <tr> 
 <td colspan="9"> 各种常用排序算法 </td> 
 </tr> 
 <tr> 
 <td> 类别 </td> 
 <td> 排序方法 </td> 
 <td colspan="3"> 时间复杂度 </td> 
 <td> 空间复杂度 </td> 
 <td> 稳定性 </td> 
 <td> 复杂性 </td> 
 <td> 特点 </td> 
 </tr> 
 <tr> 
 <td> 最好 </td> 
 <td> 平均 </td> 
 <td> 最坏 </td> 
 <td> 辅助存储 </td> 
 <td> &nbsp; </td> 
 <td> 简单 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 插入 排序 </td> 
 <td> 直接插入 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 稳定 </td> 
 <td> 简单&nbsp; </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 希尔排序 </td> 
 <td> O(N) </td> 
 <td> O(N1.3) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 选择 排序 </td> 
 <td> 直接选择 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 堆排序 </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 交换 排序 </td> 
 <td> 冒泡排序 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 稳定 </td> 
 <td> 简单 </td> 
 <td> 1、冒泡排序是一种用时间换空间的排序方法，n小时好 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级 3、最好的情况是数据本来就有序，复杂度为O(n) </td> 
 </tr> 
 <tr> 
 <td> 快速排序 </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N2) </td> 
 <td> O(log2n)~O(n)&nbsp; </td> 
 <td> 不稳定 </td> 
 <td> 复杂 </td> 
 <td> 1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。 2、划分之后一边是一个，一边是n-1个， 这种极端情况的时间复杂度就是O(N^2) 3、最好的情况是每次都能均匀的划分序列，O(N*log2N) </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 归并排序 </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(n) </td> 
 <td> 稳定 </td> 
 <td> 复杂 </td> 
 <td> 1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 基数排序 </td> 
 <td> O(d(r+n)) </td> 
 <td> O(d(r+n)) </td> 
 <td> O(d(r+n)) </td> 
 <td> O(rd+n) </td> 
 <td> 稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td colspan="9"> 注：r代表关键字基数，d代表长度，n代表关键字个数 </td> 
 </tr> 
 </tbody> 
</table>

### 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通过的代码：

> 1. public class Solution \{
> 2.     public boolean Find(int target, int \[\]\[\] array) \{
> 3.              boolean result = false;
> 4.         System.out.println(" "+array.length+" "+array\[0\].length);
> 5.         if(array.length==0 || array\[0\].length==0 )
> 6.             return result;
> 7.         int i=array.length-1,j=0;
> 8.         while(j<array\[0\].length-1 && i>0)
> 9.         \{
> 10.             if(target>array\[i\]\[j\])
> 11.                 j++;
> 12.             if(target<array\[i\]\[j\])
> 13.                 i--;
> 14.             if(target == array\[i\]\[j\])
> 15.                 return true;
> 16.         \}
> 17.         return false;
> 18.     \}
> 19. \}

本地编码：

> 1. public class SearchNum4 \{
> 2.     /\*\*
> 3.      \* @param ycy
> 4.      \*/
> 5.     public static void main(String\[\] args) \{
> 6.         // TODO Auto-generated method stub
> 7.         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\}\};
> 8.         int target1 = 5;
> 9.         int target2 = 19;
> 10.         
> 11.         if(matrix == null || matrix.length == 0|| matrix\[0\].length == 0)\{
> 12.             System.out.print("二维数组无数据");
> 13.         \}else\{
> 14.             int row = matrix.length,cols = matrix\[0\].length;
> 15.             int i = 0,j = cols-1;  //右上角的位置
> 16.             while(i<= row -1 && j>= 0)\{
> 17.                 if(target2 == matrix\[i\]\[j\])\{
> 18.                     System.out.println("存在");
> 19.                     return;
> 20.                 \}else if(target2 > matrix\[i\]\[j\] )\{
> 21.                     i++;
> 22.                 \}else\{
> 23.                     j--;
> 24.                 \}
> 25.             \}
> 26.             System.out.println("不存在");
> 27.         \}
> 28.         return;
> 29.     \}
> 30. \}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1][]

### 3 、替换空格 ###

## 题目描述 ##

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

Input:
    "A B"
    
    Output:
    "A%20B"

###  解题思路 ###

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

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

剑指offer通过的代码为：

> 1. public class Solution \{
> 2.     public String replaceSpace(StringBuffer str) \{
> 3.     StringBuffer result = new StringBuffer();
> 4.         for(int i=0;i<str.length();i++)
> 5.         \{
> 6.             if(str.charAt(i) == ' ')
> 7.                 result = result.append( "%20");
> 8.             else
> 9.                 result = result.append(str.charAt(i));
> 10.         \}
> 11.         return result.toString();
> 12.     \}
> 13. \}

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

> 1. import java.util.Arrays;
> 2. public class replaceSpace5 \{
> 3.     /\*\*
> 4.      \* @param ycy
> 5.      \*/
> 6.     public static void main(String\[\] args) \{
> 7.         // TODO Auto-generated method stub
> 8.         String input = "A B B ";
> 9.         String replace = "%20";
> 10.         String newString = "";
> 11.         char\[\] A;
> 12.         
> 13.         A=input.toCharArray();  //将字符串转换为字符数组
> 14.         
> 15.         for(int i=0;i<A.length;i++)\{
> 16.             //System.out.println(input.charAt(i));
> 17.             if(' '== A\[i\])\{
> 18.                 A\[i\] = '%';
> 19.                 newString = newString + "%20";
> 20.                 System.out.println("当前字符串： "+newString);
> 21.             \}else\{
> 22.                 newString = newString+A\[i\];
> 23.             \}
> 24.         \}
> 25.         System.out.println("最终字符串： "+newString);
> 26.         System.out.print("A字符串:");
> 27.         for(int i=0;i<A.length;i++)\{
> 28.         System.out.print(A\[i\]);
> 29.         \}
> 30.         return;
> 31.     \}
> 32. \}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2][]

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

将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<p1，这个要注意 
            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); 
    \}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3][]

###  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)

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20220118/f44f742d5cd84de29fc51d291ab16ec8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1]: /images/20220118/83eb12b27bae4fcabb25411b3828ad45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2]: /images/20220118/dbac621a715f476ebe8a56b1aa8ca44b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3]: /images/20220118/f4f4a36d35614005ae49de70e55e12a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4]: /images/20220118/a5713126c8c34119b2abe392d2551d08.png