当前位置:网站首页>记一次某公司面试题:合并有序数组
记一次某公司面试题:合并有序数组
2022-07-06 09:13:00 【三笠·阿卡曼】
来源
2021/09/24:接到某公司面试,手撕一到合并有序数组的题,当时做的差不多了,面试官时间给的相对短了一些,临界值处理有问题, 没完全写出来有些遗憾,不过至少自己思路没错,参考网上给出的资料,现整理出一个比较好的解决方式,自己也只是写了一点测试用例,若有错误,烦请指正!
具体题目不讲了,就看题目标题吧
上代码
package com.vleus.algorithm.strings;
import java.util.Arrays;
/** * @author vleus * @date 2021年09月24日 19:50 */
public class Solution {
//两个有序数组,合并成一个有序数组,要求时间复杂度为O(n)
public static int[] getNewArr(int[] arr1, int[] arr2) {
if (arr1.length == 0) {
return arr2;
}
if (arr2.length == 0) {
return arr1;
}
int i = 0;
int j = 0;
int[] newArr = new int[arr1.length + arr2.length];
for (int k = 0; k < newArr.length; k++) {
if (arr1[i] < arr2[j] && i <= arr1.length - 1) {
newArr[k] = arr1[i];
i++;
continue;
}
if (arr1[i] >= arr2[j] && j <= arr2.length - 1) {
newArr[k] = arr2[j];
j++;
continue;
}
}
return newArr;
}
public static int[] getNewArr2(int[] arr1, int[] arr2) {
int i = arr1.length + arr2.length - 1;
int i1 = arr1.length - 1;
int i2 = arr2.length - 1;
int[] newArr = new int[arr1.length+arr2.length];
while (i1 >= 0 && i2 >= 0) {
if (arr1[i1] >= arr2[i2]) {
newArr[i] = arr1[i1];
i1--;
i--;
}else{
newArr[i] = arr2[i2];
i2--;
i--;
}
}
if(i1 >= 0){
System.arraycopy(arr1,0,newArr,i1,i1+1);
}
if (i2 >= 0) {
System.arraycopy(arr2,0,newArr,i2,i2+1);
}
return newArr;
}
public static void main(String[] args) {
int[] arr1 = new int[]{
1, 3, 5, 7, 7, 8,12};
int[] arr2 = new int[]{
2, 4, 6, 8, 8};
int[] newArr2 = getNewArr2(arr1, arr2);
System.out.println(Arrays.toString(newArr2));
}
}
边栏推荐
- MySQL19-Linux下MySQL的安装与使用
- MNIST implementation using pytoch in jupyter notebook
- CSDN问答标签技能树(二) —— 效果优化
- [recommended by bloggers] background management system of SSM framework (with source code)
- [Li Kou 387] the first unique character in the string
- Water and rain condition monitoring reservoir water and rain condition online monitoring
- MySQL23-存储引擎
- Why is MySQL still slow to query when indexing is used?
- MySQL21-用戶與權限管理
- Redis的基础使用
猜你喜欢
【博主推荐】asp.net WebService 后台数据API JSON(附源码)
MySQL19-Linux下MySQL的安装与使用
【博主推荐】C#MVC列表实现增删改查导入导出曲线功能(附源码)
A trip to Macao - > see the world from a non line city to Macao
Mysql27 - Optimisation des index et des requêtes
[recommended by bloggers] C # generate a good-looking QR code (with source code)
MySQL28-数据库的设计规范
Bytetrack: multi object tracking by associating every detection box paper reading notes ()
MySQL transaction log
Why is MySQL still slow to query when indexing is used?
随机推荐
Win10: how to modify the priority of dual network cards?
MySQL24-索引的数据结构
Invalid default value for 'create appears when importing SQL_ Time 'error reporting solution
MySQL31-MySQL事务日志
Database middleware_ MYCAT summary
Mysql30 transaction Basics
MySQL30-事务基础知识
MySQL27-索引優化與查詢優化
Global and Chinese market of operational amplifier 2022-2028: Research Report on technology, participants, trends, market size and share
[BMZCTF-pwn] 11-pwn111111
Postman uses scripts to modify the values of environment variables
C language string function summary
[C language] deeply analyze the underlying principle of data storage
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
Isn't there anyone who doesn't know how to write mine sweeping games in C language
Ubuntu 20.04 安装 MySQL
MySQL29-数据库其它调优策略
Windchill configure remote Oracle database connection
MNIST implementation using pytoch in jupyter notebook
CSDN博文摘要(一) —— 一个简单的初版实现