精华内容
下载资源
问答
  • 给定一个数组 nums ,其中包含正数与负数,并且已经按照从小到大排列,请按照绝对值从小到大重新排列 例如: nums = {-9,-8,-7,-6,1,2,3,4}; 排序后 nums = {1,2,3,4,-6,-7,-8,-9} ; 思路: 找到正负...

    题目

      给定一个数组 nums ,其中包含正数与负数,并且已经按照从小到大排列,请按照绝对值从小到大重新排列

      例如: 

    nums = {-9,-8,-7,-6,1,2,3,4};

     排序后

    nums = {1,2,3,4,-6,-7,-8,-9} ;

     

     

    思路

       找到正负交界处,设最小的正数下标为 i ,最大的负数下标为 j  , 依次进行判断,绝对值小的数放入 list 中 

      注: 这个是允许使用新空间的

     

     

    Java代码如下:

    public class Main{
    
      @Test
        public void test40(){
            int[]  nums = {-9,-8,-7,-6,1,2,3,4};
            sort(nums);
        }
    
    
        public void sort(int[]  nums){
            List<Integer>  result = new ArrayList<>();
            int  zeroIndex = -1;
            for(int i=0;i<nums.length-1;i++){
                if(nums[i] < 0 && nums[i+1]>=0){
                    zeroIndex = i;  //正负分界
                }
            }
    
            int  i = zeroIndex + 1; // 最小的正数下标
            int  j = zeroIndex; // 最大的负数下标
    
            while (i<nums.length && j>=0){
                if(nums[i] < Math.abs(nums[j])){
                    result.add(nums[i]);
                    i++;
                }else {
                    result.add(nums[j]);
                    j--;
                }
            }
    
            while (i<nums.length){
                result.add(nums[i++]);
            }
    
            while (j>=0){
                result.add(nums[j--]);
            }
    
            for(int a:result){
                System.out.print(a+",");
            }
    
    
    
    
    
        }
    
    
    
    
    
    }

     

    展开全文
  • Java语言高分悬赏:将一个数组的偶数位的元素按照升序排序,奇数位的元素按照绝对值排序
  • 2、若按照1的方法查找失败,则两个数肯定都为非负数或都为负数。 pair one_nonnegative_one_negative(int* num, int length, int k) { pair res(length-1, length-1);//非负、负 while (res.

    题目:EPI


    提示:

    1、假设和为k的两个数,一个为非负数一个为负数,找出其下标。

    2、若按照1的方法查找失败,则两个数肯定都为非负数或都为负数。


    pair<int, int> one_nonnegative_one_negative(int* num, int length, int k)
    {
    	pair<int, int> res(length-1, length-1);//非负、负
    	while (res.first >= 0 && num[res.first] < 0)
    		res.first--;
    	while (res.second >= 0 && num[res.second] >= 0)
    		res.second--;
    	while (res.first >= 0 && res.second >= 0)
    	{
    		if (num[res.first] + num[res.second] == k)
    			return res;
    		else if (num[res.first] + num[res.second] < k)//负数左移
    		{
    			do{
    				res.second--;
    			} while (res.second >= 0 && num[res.second] >= 0);
    		}
    		else//非负数左移
    		{
    			do{
    				res.first--;
    			} while (res.first >= 0 && num[res.first] < 0);
    		}
    	}
    	return pair<int, int>(-1, -1);
    
    }
    
    pair<int, int> both_the_same_sign(int* num, int length, int k)
    {
    	if (k >= 0)//两个非负数
    	{
    		pair<int, int> res(0, length - 1);
    		while (res.first <length && num[res.first] < 0)
    			res.first++;
    		while (res.second >= 0 && num[res.second] < 0)
    			res.second--;
    		while (res.first <= res.second)
    		{
    			if (num[res.first] + num[res.second] == k)
    				return res;
    			else if (num[res.first] + num[res.second] < k)
    			{
    				do{
    					//
    					res.first++;
    				} while (res.first <= res.second && num[res.first] < 0);
    			}
    			else
    			{
    				do{
    					res.second--;
    				} while (res.first <= res.second && num[res.second] < 0);
    			}
    		}
    		return pair<int, int>(-1, -1);
    
    	}
    	else//两个负数
    	{
    		pair<int, int> res(0, length - 1);
    		while (res.first <length && num[res.first] >= 0)
    			res.first++;
    		while (res.second >= 0 && num[res.second] >= 0)
    			res.second--;
    		while (res.first <=res.second)
    		{
    			if (num[res.first] + num[res.second] == k)
    				return res;
    			else if (num[res.first] + num[res.second] < k)
    			{
    				do{
    					res.second--;
    				} while (res.first <= res.second && num[res.second] >= 0);
    			}
    			else
    			{
    				do{
    					res.first++;
    				} while (res.first <= res.second && num[res.first] >= 0);
    			}
    		}
    		return pair<int, int>(-1, -1);
    	}
    }
    
    pair<int, int> find_sum_is_k(int* num, int length, int k)
    {
    	pair<int, int> res(-1, -1);
    	if (num == nullptr || length <= 0)
    		throw new exception("error");
    	res = one_nonnegative_one_negative(num, length, k);//一个非负,一个负
    	if (res.first == -1 && res.second == -1)
    		res = both_the_same_sign(num, length, k);//两个一样符号
    	return res;
    }


    展开全文
  • 给已排序数组(有正有负)按照绝对值大小进行排序,给出尽可能最优的时间复杂度和空间复杂度 思路 数组大概是这样,{-20, -9, -4, -1, -1, 0, 3, 5, 19} 如果负数且有正数存在,那么绝对值最小的一...

    前言

    最近在面试中一遇到算法题就懵了,总是能巧妙避过最优解方法给出最朴素、最贪心的答案,然后面试完脑子又能一闪而过更好的思路。

    想起那么一句话叫“事前猪一样,事后诸葛亮”?

    题目

    已排序数组(有正有负)按照绝对值大小进行排序,给出尽可能最优的时间复杂度和空间复杂度

    思路

    数组大概是这样,{-20, -9, -4, -1, -1, 0, 3, 5, 19}

    如果负数且有正数存在,那么绝对值最小的一定在中间绝对值最大的一定在左右两侧。那么可以有两种思路

    额外设置一个大小为n的数组(空间复杂度O(n)O(n)

    1. 先找到绝对值最小的(二分查找,时间复杂度O(log(n))O(log(n))),分别向左右两边进行遍历、比较,按绝对值从小到大赋值到新数组(时间复杂度O(n)O(n)),总时间复杂度为O(n)O(n)
    2. 设置l, r指针,从左右两端向里进行遍历、比较,按绝对值从大到小的顺序赋值到新数组(时间复杂度O(n)O(n))。

    方法一在面试的时候花了几十分钟写完,面试完想了想,两分钟写了方法二。

    解法

    这里贴一下方法二的代码:

    void abs_sort(vector<int> & nums){
        if(nums.empty())
            return ;
    
        int n = nums.size();
        int l = 0, r = n - 1, p = n - 1;
        vector<int> ans(n);
        
        while(l <= r){
            if(abs(nums[l]) > abs(nums[r]))
                ans[p--] = nums[l++];
            else 
                ans[p--] = nums[r--];
        }
        nums = ans;
    }
    
    int main() {
        vector<int> nums = {-20, -4, -1, -1, 3, 4, 5, 7, 9, 10};
        abs_sort(nums);
        
        for(auto n : nums)
            cout<<n<<" ";
        cout<<endl;
    
        return 0;
    }
    

    待续

    直觉上,面试出的编程题空间复杂度应该还可以再优化到O(1)O(1),但具体思路还没想到,以后补上。

    展开全文
  • =100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例,所有的数的绝对值都不相等。 Input 输入数据有多组,每组占一行,每行的第一个数字为n,接着是n个整数,n=0表示输入数据的结束,不做处理。...

    Problem Description
    输入n(n<=100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例,所有的数的绝对值都不相等。

    Input
    输入数据有多组,每组占一行,每行的第一个数字为n,接着是n个整数,n=0表示输入数据的结束,不做处理。

    Output
    对于每个测试实例,输出排序后的结果,两个数之间用一个空格隔开。每个测试实例占一行。

    注意java中结构体数组如何定义,以及如何建立结构体数组 ,如何对结构体数组进行自定义排序!!!

    !!!!!!!!!!!!!!!!

    import java.text.DecimalFormat;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Scanner;
    
    class number implements Comparable<number> //number类相当于结构体,顺便定义排序方式
    {
    	int key,abs_key;
    	public number(int key,int abs_key)
    	{
    		this.key = key;
    		this.abs_key = abs_key;
    	}
    	public int compareTo(number a)
        {
    		return this.abs_key-a.abs_key;
    	}
    }
    public class Main {
    
    	final static double pi = 3.1415927;
    	final static int count[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    	
    	public static void main(String[] args) {
    		Scanner cin = new Scanner(System.in);
    		while(true)
    		{
    			int n = cin.nextInt();
    			if(n==0)
    				break;
    			number a[] = new number[n];//注意两个new
    			for(int i=0;i<n;i++)
    			{
    				int tmp = cin.nextInt();
    				a[i] = new number(tmp,Math.abs(tmp));//第二个new
    			}
    			Arrays.sort(a);
    			System.out.print(a[n-1].key);
    			for(int i=n-2;i>=0;i--)
    				System.out.print(" "+a[i].key);
    			System.out.println();
    		}
    		cin.close();
    	}
    
    }
    
    
    
    展开全文
  • 数组排序

    2018-08-12 17:00:02
    按照绝对值对数组进行排序: 如:[-20, -5, 10, 15] 排序后:[-5, 10, 15, -20] 输入:数组 输出:数组 def sorted_li(): a = input("请输入数组:") print(a) a = a.split(",") ...
  • 二维数组排序

    2018-12-13 19:57:16
    如果出现有的行平均值相同的情况,则按照原顺序输出。 输入与输出要求: 输入一个整数n代表矩阵的行数(列数),n的范围是1—100。然后输入n*n个整数,即此矩阵的元素。矩阵元素的绝对值不会超过1000。输出经过行...
  • 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例 分析 这道题我想了好久,知道平衡二叉树进行...
  • 题目 ... 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。...对数组按照绝对值进行排序 将绝对值大的负
  • 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的...
  • lintcode 在排序数组中找最接近的K个数描述样例思路代码 描述 给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与...数组中元素的绝对值不...
  • 由此的具体方案,对A和B进行排序,这在A中的第i个数分配B中第i个数进行求差值。 2.贪心选择性:  给A中最小的数分配一个B中最小的数,然后在剩余的数组中重复配对,就能得到最小的绝对差值和  证明:  取i,j ...
  • 描述给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度...给定数组的长度是正整数, 不会超过 10^4数组中元素的绝对值不会超过...
  • 题意:对数组排序,顺序是按照数组的平均值,即按照一个元素和平均值相减的绝对值的大小来排序。。。本例按这个绝对值递增排序 解题思想:先求出这个数组的平均值,如果 a<b,那么 a-avg<b-avg,这样,abs(a-...
  • 考虑到原数组已经是排好序的,所以可以采用双指针,从两段开始遍历,这样出来的元素就是按照绝对值排序的了,这时程序的时间复杂度为O(N)。C++的实现代码如下: class Solution { public: vector<int> ...
  • 给一个目标数 ​target​, 一个非负整数 ​k​, 一个按照升序排列的数组 ​A​。在​A​中找与​target​最接近的...给定数组的长度是正整数, 不会超过 10​^4​​数组中元素的绝对值不会超过 10​^4在线评测地址:L...
  • 二叉搜索树的中序遍历是升序序列,题目给定的数组按照升序排序的有序数组,因此可以确保数组是二叉搜索树的中序遍历序列。 给定二叉搜索树的中序遍历,是否可以唯一地确定二叉搜索树?答案是否定的。
  • 108. 将有序数组转换为二叉搜索树题目将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定有序...
  • 题目 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点...二叉搜索树的中序遍历是升序序列,题目给定的数组按照升序排序的有序数组,因此可以确保数
  • 目录 题目 解题 方法一、中序遍历 ...将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。...分析:二叉搜索树的中序遍历是升序排列的,题目给定的数组按照升序排序的有序数组,...
  • POJ1990 (树状数组

    2017-11-29 00:21:56
    对于树状数组的理解不透+不会转化题解:显然是要按照v排序的,那么首先在On情况下是可以完成max(vi,vj)的操作,对于某个牛i,我们只需考虑i之前的,那么i之前的牛我们需要知道每只牛j ,abs(dis(i) - dis(j)),去掉...
  • 二叉搜索树的中序遍历是升序序列,题目给定的数组按照升序排序的有序数组,因此可以确保数组是二叉搜索树的中序遍历序列。但是只给了中序遍历序列不能确定唯一的二叉树。 可以看做是在数组挑一个做父亲...
  • 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的...
  • 这道题目目的是将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。所谓的平衡二叉树,是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。如图所示: 拿到题目似乎无从下手,要建立一个...
  • 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 二叉搜索树: 二叉查找树(Binary Search Tree),也...
  • 将一个按照升序排序的有序数组,转换为一颗高度平衡二叉搜索树。 一个高度平衡二叉树又称为AVL树是指一个二叉树每个节点的左右两个子树的高度的绝对值不超过1 例如: [-10, -3, 0, 5, 9] ​ 一个可能的答案是:[0, -...
  • 按照ti排序 |p[i]-p[j]|<=2*(t[i]-t[j]) 然后去绝对值变为三维偏序 发现后两个式子可以推出ti<tj 所以就变成二维偏序 按照一个排序套线段树就可以了 代码非常好写 代码: #include <bits/stdc++....

空空如也

空空如也

1 2 3 4
收藏数 79
精华内容 31
关键字:

数组按照绝对值排序