c++ 绝对不同数

enyaitl3 于 2023-07-01 发布在其他

关注(0)|答案(5)|浏览(115)

我正在写一个关于C++编码的练习。这里的问题：
给出一个由N个数字组成的非空零索引数组A。数组按非降序排序。此数组的绝对非重复计数是数组元素中的非重复绝对值的数量。
例如，考虑数组A，使得：

A[0] = -5
A[1] = -3
A[2] = -1
A[3] =  0
A[4] =  3
A[5] =  6

这个数组的绝对非重复计数是5，因为这个数组的元素中有5个不同的绝对值，即0，1，3，5和6。
写一个函数：
int solution(vector<int> &A);
给定一个由N个数字组成的非空零索引数组A，返回数组A的绝对非重复计数。
例如，给定数组A，使得：

A[0] = -5
A[1] = -3
A[2] = -1
A[3] =  0
A[4] =  3
A[5] =  6

如上所述，该函数应该返回5。
假设：
N是范围[1..100,000]内的整数;
数组A的每个元素是范围[−2,147,483,648..2,147,483,647]内的整数;
数组A以非降序排序。
复杂度：
预期的最坏情况时间复杂度为O(N);
预期的最坏情况空间复杂度为O(N)，超出输入存储（不计算输入参数所需的存储）。
可以修改输入数组的元素。
我写了下面的代码，我没有发现我的代码中有任何问题，但它就是不通过。

#include <algorithm>
#include <vector>
#include <cmath>

int solution(vector<int> &A) {
    int N(A.size());
    vector<long long> B(N,0);
    int counter(1);
    //int index(0);
    int move1(0);
    int move2(N-1);
    if(N==1)
        {return 1;}
    if(N==0)
        {return 0;}
    if(N==2)
        {
            if(abs(A[0])==abs(A[1]))
                {return 1;}
            else{return 2;}
        }

    for (int i = 0 ; i < N ; ++i)
        {
            B[i]=abs((long long )A[i]);
        }

    while(move1<move2)
        {
            if(B[move1]==B[move1+1])
                {move1+=1;}

            else if(B[move2]==B[move2]-1)
                {move2-=1;}

            else if(B[move1]>B[move2])
                {
                    counter+=1;
                    move1+=1;
                }
            else if(B[move1]<B[move2])
                {
                    counter+=1;
                    move2-=1;
                }
            else{move1+=1;}
        }

    return counter;
}

下面是性能的链接，https://codility.com/demo/results/trainingUT9QAN-JMM/有一些错误，但我不能弄清楚它的细节，如果有人能帮助我与我的代码，我会非常感激！
谢谢！

c++

来源：https://stackoverflow.com/questions/34933610/absolute-distinct-numbers

5条答案

按热度按时间

7uzetpgm1#

您可能希望有一个迭代的解决方案。从两端开始，向内朝0的方向工作。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

size_t solution( const std::vector< int > & A )
{
    std::vector< int >::const_iterator f( A.begin() );
    std::vector< int >::const_reverse_iterator b( A.rbegin() );

    size_t result = 0;
    if( A.size() )
        for( ; ( f != A.end() ) && ( b != A.rend() ); )
        {
            if( *f >= 0 )
                return result + ( ( A.end() - f ) - ( b - A.rbegin() ) );
            else if( *b <= 0 )
                return result + ( ( A.rend() - b ) - ( f - A.begin() ) );
            else if( *f == -*b )
                ++result, ++f, ++b;
            else if( *f > -*b )
                ++result, ++b;
            else
                ++result, ++f;
        }
    return result;
}

int main( int, char ** )
{
    std::cout << solution( std::vector< int >{ -5, -3, -1, 0, 3, 6} ) << std::endl;
    std::cout << solution( std::vector< int >{ -5, -3, -1, 0, 1, 3, 6} ) << std::endl;
    std::cout << solution( std::vector< int >{ -5, -3, -1, 0, 2, 3, 6} ) << std::endl;
    std::cout << solution( std::vector< int >{ -5, -3, -1, 3, 6} ) << std::endl;
    std::cout << solution( std::vector< int >{ -5, -3, -1, 0, 3, 4, 5} ) << std::endl;
    return 0;
}

赞(0）回复(0）举报 2023-07-01

ny6fqffe2#

100% Ruby解决方案

def solution(a)
  a.each_with_object({}){ |el, acc| acc[el.abs] = true }.size
end

赞(0）回复(0）举报 2023-07-01

wkyowqbh3#

使用Java 8流获得100/100。

return (int) Arrays.stream(A).map(Math::abs)
            .distinct().count();

赞(0）回复(0）举报 2023-07-01

ecfsfe2w4#

def solution(A):
 
    # Creates an empty hashset
    s = set()
    n = len(A)
     
    
    res = 0
    for i in range(n):
     
        # If not present, then put it in
        # hashtable and increment result
        if (A[i] not in s):
            s.add(A[i])
            res += 1
     
    return res

赞(0）回复(0）举报 2023-07-01

nnsrf1az5#

Java an alternative solution by using custom iterator

import java.util.Iterator;

import static java.lang.String.format;

public final class AbsDistinct {
    private AbsDistinct() {
        super();
    }

    public static int nrOfAbsDistinctNumbers(
            final int[] sortedAscArray) {
        final Iterator<Long> iterator = new AbsDistinctIterator(sortedAscArray);
        int count = 0;
        while (iterator.hasNext()) {
            iterator.next();
            count++;
        }
        return count;
    }

    private static final class AbsDistinctIterator implements Iterator<Long> {
        private final int[] sortedArray;

        private int head;

        private int tail;

        AbsDistinctIterator(int[] sortedArray) {
            this.sortedArray = sortedArray;
            this.head = 0;
            this.tail = sortedArray.length - 1;
        }

        @Override
        public boolean hasNext() {
            return head <= tail;
        }

        @Override
        public Long next() {
            final long headVal = Math.abs((long) sortedArray[head]);
            final long tailVal = sortedArray[tail];
            if (headVal > tailVal) {
                nextHeadVal();
                return headVal;
            }
            if (headVal == tailVal) {
                nextHeadVal();
                nextTailVal();
                return headVal;
            }
            nextTailVal();
            return tailVal;
        }

        private void nextHeadVal() {
            final int headVal = sortedArray[head];
            while (head <= tail && sortedArray[head] == headVal) {
                head++;
            }
            ;
        }

        private void nextTailVal() {
            final int tailVal = sortedArray[tail];
            while (tail >= head && sortedArray[tail] == tailVal) {
                tail--;
            }
            ;
        }
    }

    private static void assertCorrectNrOfAbsDistinctNumbers(final int[] array, final int expected) {
        final var calculated = nrOfAbsDistinctNumbers(array);
        if (calculated != expected) {
            throw new AssertionError(format("expected '%d' - calculated '%d'", expected, calculated));
        }
    }

    public static void main(String[] args) {
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                        -5, -3, -1, 0, 3, 6
                },5
        );
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -2147483648, 5, 2147483647
        }, 3);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -2147483648, 5, 5, 5, 5, 5, 5, 5, 2147483647
        }, 3);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -2147483647
        }, 1);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -1, 0, 1, 2
        }, 3);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -1, 2
        }, 2);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -1, -2
        }, 2);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                1, 2
        }, 2);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                1
        }, 1);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -1
        }, 1);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -2, 1
        }, 2);
        assertCorrectNrOfAbsDistinctNumbers(new int[]{
                -5, -4, -3, -2, -1, 6, 7, 8, 9
        }, 9);
    }
}

赞(0）回复(0）举报 2023-07-01

我来回答

c++ 绝对不同数

5条答案

相关问题

热门标签

最新问答